MCA-118 Theory of Computations Notes cover all 4 units of this GGSIPU MCA Semester 2 Core Elective I paper in one 67-page printed book: 48 topics, 30 diagrams, 40 short questions with answers and 40 long-answer exam questions. They follow the MCA syllabus that applies from academic session 2025-26 onwards.
Written by Prateek Talwar, Founder, Unnati Educations · Reviewed by Ritik Rawat, B.Tech, Senior Full Stack Developer · Checked against the GGSIPU MCA Scheme of Examination and Detailed Syllabus (A.S. 2025-26 onwards), verified 13 Oct 2026 · Updated 14 October 2026 · Editorial policy
Scheme: MCA (2 years), affiliated institutes, A.S. 2025-26 onwards | Applies to: batches from academic session 2025-26 onwards | Verified against: MCA Scheme of Examination and Detailed Syllabus (ipu.ac.in PDF), approved by BoS of USIC&T on 28 Jul 2025
MCA-118 Theory of Computations at a glance: GGSIPU MCA Sem 2 credits, units and exam pattern
MCA-118 is one of ten Core Elective I papers in Semester 2. Figures below are from the official MCA scheme PDF.
| Code and title | MCA-118 Theory of Computations |
|---|---|
| Semester, category, credits | MCA (2 years) Sem 2, Core Elective I; L 3, T/P 1, 4 credits |
| Teaching hours by unit | 14 · 12 · 10 · 8 across Units 1-4 (44 hours) |
| Marks | 100: 40 internal + 60 end-term (paper total 100, end-term paper 60, so 40 is internal) |
| Question paper pattern | Q1 compulsory, short-answer, whole syllabus: 12 marks. Two questions per unit, attempt one, 12 marks each (12 + 48 = 60 marks) |
| Applies to | Batches from academic session 2025-26 onwards |
| Pre-requisites | Discrete Structures; writing formal mathematical proofs |
| Matching lab | MCA-168 Theory of Computations Lab: T/P 2, 1 credit (not in this book) |
All other papers of this semester are listed under GGSIPU MCA Semester 2 papers.
MCA-118 Theory of Computations Notes unit-wise: 48 topics, 30 diagrams and 80 exam questions across 4 units
These GGSIPU MCA Sem 2 Theory of Computations notes follow the four official units, each ending with a Quick Revision Table and 20 exam questions. Notes for every other MCA paper sit under GGSIPU MCA notes. The sample PDF button at the top shows the layout.
MCA-118 Unit 1: Introduction to Automata and Regular Language
Pages 4-23 (20 pages, 16 sections, 12 diagrams), the biggest unit. It moves from alphabets, strings and Σ* to DFA, NFA and ε-NFA designs, subset construction, partition-method minimisation, Mealy and Moore conversions, regular expression identities, Kleene's and Arden's theorems and the pumping lemma, ending with click-by-click JFLAP steps.
| State (remainder) | On 0 | On 1 |
|---|---|---|
| R0 (start and final) | R0 | R1 |
| R1 | R2 | R0 |
| R2 | R1 | R2 |
Quick look: DFA for binary numbers divisible by 3 (from page 9)
- State (remainder)
- R0 (start and final)
- On 0
- R0
- On 1
- R1
- State (remainder)
- R1
- On 0
- R2
- On 1
- R0
- State (remainder)
- R2
- On 0
- R1
- On 1
- R2
Bit b after remainder r gives (2r + b) mod 3; 110 (six) ends in R0 and is accepted.
MCA-118 Unit 2: Context Free Language and Pushdown Automata
Pages 24-39 (16 pages, 12 sections, 7 diagrams). A table of ten standard CFGs, leftmost and rightmost derivations, the id + id * id ambiguity and its E, T, F fix, simplification, then worked CNF and GNF conversions. The PDA half designs machines for aⁿbⁿ, wcwᴿ and wwᴿ and proves aⁿbⁿcⁿ is not context-free.
| Point | CNF | GNF |
|---|---|---|
| Form | A → BC or A → a | A → aα, α ∈ V* |
| Steps to derive a string of length n | 2n − 1 | n |
| Left recursion | Allowed | Impossible |
| Main use | CYK algorithm, pumping lemma proof | Building PDAs, top-down parsing |
Quick look: Chomsky Normal Form vs Greibach Normal Form (from page 32)
- Point
- Form
- CNF
- A → BC or A → a
- GNF
- A → aα, α ∈ V*
- Point
- Steps to derive a string of length n
- CNF
- 2n − 1
- GNF
- n
- Point
- Left recursion
- CNF
- Allowed
- GNF
- Impossible
- Point
- Main use
- CNF
- CYK algorithm, pumping lemma proof
- GNF
- Building PDAs, top-down parsing
MCA-118 Unit 3: Turing Machines and Computability Theory
Pages 40-53 (14 pages, 10 sections, 6 diagrams). The TM 7-tuple, a marking machine for aⁿbⁿ traced cell by cell, unary addition, and a closure table for recursive and RE languages. Multi-tape, multidimensional and non-deterministic TMs are shown equal in power, followed by the Universal TM encoding, PCP and MPCP, reductions and the Chomsky hierarchy.
| i | List A (wᵢ) | List B (xᵢ) |
|---|---|---|
| 1 | 1 | 111 |
| 2 | 10111 | 10 |
| 3 | 10 | 0 |
Quick look: Post Correspondence Problem instance with a solution (from page 48)
- i
- 1
- List A (wᵢ)
- 1
- List B (xᵢ)
- 111
- i
- 2
- List A (wᵢ)
- 10111
- List B (xᵢ)
- 10
- i
- 3
- List A (wᵢ)
- 10
- List B (xᵢ)
- 0
The index sequence 2, 1, 1, 3 spells 101111110 on both lists, so this instance is solvable.
MCA-118 Unit 4: Complexity Theory
Pages 54-67 (14 pages, 10 sections, 5 diagrams). Big-O and related notation, DTIME and NTIME, the class P, polynomial verifiers for CLIQUE, SUBSET-SUM and SAT, Cook-Levin and a 3SAT to CLIQUE reduction. Savitch's theorem, PSPACE, L and NL, and the probabilistic classes BPP, RP and ZPP close the unit.
| Machine | Idea | Time |
|---|---|---|
| Single-tape M₁ | Cross off one 0 and one 1 per sweep | O(n²) |
| Single-tape M₂ | Check parity, then cross off every other 0 and 1 | O(n log n) |
| Two-tape M₃ | Copy the 0s to tape 2, match each 1 against them | O(n) |
Quick look: deciding {0ᵏ1ᵏ} on different Turing machine models (from page 56)
- Machine
- Single-tape M₁
- Idea
- Cross off one 0 and one 1 per sweep
- Time
- O(n²)
- Machine
- Single-tape M₂
- Idea
- Check parity, then cross off every other 0 and 1
- Time
- O(n log n)
- Machine
- Two-tape M₃
- Idea
- Copy the 0s to tape 2, match each 1 against them
- Time
- O(n)
The Halting Problem in computability theory: excerpt from page 47 of the MCA-118 notes
Excerpt from page 47
Decidable and undecidable problems
Some questions about machines always have an algorithm. Does a DFA accept w? Is the language of a DFA empty or infinite? Are two DFAs equivalent? Does a CFG generate w (the CYK algorithm)? Is the language of a CFG empty or finite? Is a string in a context-sensitive language? All of these are decidable.
Others have no algorithm at all: does a Turing machine M halt on w, does M accept w, is L(M) empty, is a CFG ambiguous, do two CFGs generate the same language, is L(CFG) equal to Σ*, the Post Correspondence Problem, and whether L(M) is regular (Rice's theorem).
The problem
Given a Turing machine M and an input w, does M halt on w? As a language, HALT_TM = {⟨M, w⟩ | M halts on input w}.
Theorem
The Halting Problem is undecidable. HALT_TM is recursively enumerable but not recursive.
Proof by diagonalisation (contradiction)
- Assume a TM H decides HALT_TM: H(⟨M, w⟩) says "yes" if M halts on w and "no" otherwise, and H always halts.
- Build a new TM D that takes the code ⟨M⟩ of a machine and runs H on ⟨M, ⟨M⟩⟩, asking whether M halts on its own code. If H says yes, D enters an infinite loop. If H says no, D halts.
- Now run D on its own code ⟨D⟩.
- If D halts on ⟨D⟩, then H(⟨D, ⟨D⟩⟩) = yes, so by construction D loops. Contradiction.
- If D does not halt on ⟨D⟩, then H says no, so by construction D halts. Contradiction.
- Both cases are impossible, so H cannot exist and the Halting Problem is undecidable.
The page shows machine D as a diagram: input ⟨M⟩ is copied to ⟨M, ⟨M⟩⟩, passed to the assumed decider H, and the "yes" branch leads to "loop forever" while the "no" branch leads to "halt".
Why HALT_TM is still recognisable
A Universal Turing Machine can simulate M on w and accept if M halts, so HALT_TM is RE. Since it is RE but not recursive, its complement is not RE, by the theorem that a language is recursive whenever both it and its complement are RE.
MCA-118 exam corner: 40 short-answer and 40 long-answer questions by unit
Each unit has 10 answered short questions and 10 long questions. The notes label them "2.5 marks" and "12.5 marks"; the 2025-26 paper uses 12-mark questions, so treat the labels as answer-length guides.
| Unit | Short (answered) | Long | Diagrams |
|---|---|---|---|
| Unit 1 | 10 | 10 | 12 |
| Unit 2 | 10 | 10 | 7 |
| Unit 3 | 10 | 10 | 6 |
| Unit 4 | 10 | 10 | 5 |
MCA-118 exam questions in the notes, by unit
- Unit
- Unit 1
- Short (answered)
- 10
- Long
- 10
- Diagrams
- 12
- Unit
- Unit 2
- Short (answered)
- 10
- Long
- 10
- Diagrams
- 7
- Unit
- Unit 3
- Short (answered)
- 10
- Long
- 10
- Diagrams
- 6
- Unit
- Unit 4
- Short (answered)
- 10
- Long
- 10
- Diagrams
- 5
The MCA-118 notes answer 40 short-answer questions and set 40 long-answer questions across 4 units, with 30 diagrams.
One exam-style question per unit:
- Unit 1: Differentiate between ∅, {ε} and ε. Pointer: ε is a string of length 0, {ε} holds one string, ∅ holds none.
- Unit 2: Is an NPDA more powerful than a DPDA? Justify. Pointer: yes; wwᴿ needs a guess of the middle, so DCFL ⊂ CFL, unlike DFA = NFA.
- Unit 3: Is a non-deterministic TM more powerful than a deterministic TM? Pointer: no; a DTM simulates it breadth-first, only slower.
- Unit 4: Differentiate between NP-hard and NP-complete. Pointer: NP-complete is NP-hard and also in NP; the Halting Problem is NP-hard only.
More practice sits in the MCA-118 important questions.
Who writes and checks the MCA-118 Theory of Computations notes?
- Prateek Talwar, author and editor: Founder, Unnati Educations; Associate Company Secretary (ACS), ICSI, membership no. 58704, since 15 May 2019; B.Com, University of Delhi (School of Open Learning), 2012. Author bio
- Ritik Rawat, subject reviewer: B.Tech; Senior Full Stack Developer, Unnati Educations.
On MCA-118 the review covers the technical working: transition tables, ID traces and conversions such as the subset construction (page 12) and the aⁿbⁿ TM trace (page 42). These MCA-118 Theory of Computations IPU notes are mapped to the GGSIPU MCA scheme for A.S. 2025-26 onwards and were last updated on 14 October 2026. See our editorial policy.
The same team prepares GGSIPU important questions for every course.
Do the MCA-118 notes cover the full GGSIPU syllabus?
Yes. Every topic named in the four official MCA-118 units has its own section in the notes, including JFLAP, MPCP and probabilistic computation.
| Official unit | Official topics | Where in the notes | Status |
|---|---|---|---|
| Unit I: Introduction to Automata and Regular Language | Overview, applications; strings, languages; FSM; DFA, NFA, €-Closure; equivalence of DFAs and NFAs; minimization; Mealy and Moore; regular expressions, identities; Kleen's and Arden's theorems; closure; pumping lemma; non-regular languages; JFLAP | Sections 1-16, pages 5-21 | Covered |
| Unit II: Context Free Language and Pushdown Automata | Grammar, CFG; LMD and RMD; derivation tree; ambiguity and removal; simplification; CNF, GNF; PDA (deterministic and nondeterministic); CFG-PDA equivalence; closure; pumping lemma; non-CFLs | Sections 1-12, pages 25-37 | Covered |
| Unit III: Turing Machines and Computability Theory | Turing machine; recursive and RE languages, closure; multi-tape, multidimensional, non-deterministic TMs; Universal TM; Church-Turing thesis; decidability; halting problem; PCP, modified PCP; reducibility; Chomsky classification | Sections 1-10, pages 41-51 | Covered |
| Unit IV: Complexity Theory | Time and space measure; time complexity; DTIME(t(n)), NTIME(t(n)); polynomial verifier; P and NP; space complexity; PSPACE; Savitch theorem; L, NL; probabilistic computation | Sections 1-10, pages 55-65 | Covered |
MCA-118 official syllabus mapped to the notes
- Official unit
- Unit I: Introduction to Automata and Regular Language
- Official topics
- Overview, applications; strings, languages; FSM; DFA, NFA, €-Closure; equivalence of DFAs and NFAs; minimization; Mealy and Moore; regular expressions, identities; Kleen's and Arden's theorems; closure; pumping lemma; non-regular languages; JFLAP
- Where in the notes
- Sections 1-16, pages 5-21
- Status
- Covered
- Official unit
- Unit II: Context Free Language and Pushdown Automata
- Official topics
- Grammar, CFG; LMD and RMD; derivation tree; ambiguity and removal; simplification; CNF, GNF; PDA (deterministic and nondeterministic); CFG-PDA equivalence; closure; pumping lemma; non-CFLs
- Where in the notes
- Sections 1-12, pages 25-37
- Status
- Covered
- Official unit
- Unit III: Turing Machines and Computability Theory
- Official topics
- Turing machine; recursive and RE languages, closure; multi-tape, multidimensional, non-deterministic TMs; Universal TM; Church-Turing thesis; decidability; halting problem; PCP, modified PCP; reducibility; Chomsky classification
- Where in the notes
- Sections 1-10, pages 41-51
- Status
- Covered
- Official unit
- Unit IV: Complexity Theory
- Official topics
- Time and space measure; time complexity; DTIME(t(n)), NTIME(t(n)); polynomial verifier; P and NP; space complexity; PSPACE; Savitch theorem; L, NL; probabilistic computation
- Where in the notes
- Sections 1-10, pages 55-65
- Status
- Covered
Official source: GGSIPU MCA Scheme of Examination and Detailed Syllabus, A.S. 2025-26 onwards (ipu.ac.in).
Every course in GGSIPU notes is mapped to its official PDF the same way.
How to write MCA-118 answers: DFA designs, subset-construction tables and pumping-lemma proofs
MCA-118 marks go mainly to constructions and proofs; the notes fix a method for each:
- DFA design: say what each state remembers, and add a dead state so the DFA is complete (page 9).
- NFA to DFA: one table row per new subset, unions written in full, final subsets marked * (page 12).
- Grammar simplification: ε-productions, then unit productions, then useless symbols, non-generating before unreachable (page 29).
- Turing machines: a transition table plus ID traces for one accepted and one rejected string (page 42).
Worked example: prove L = {aⁿbⁿ | n ≥ 0} is not regular (page 20)
- Assume L is regular with pumping length p.
- Choose
w = aᵖbᵖ, so |w| = 2p ≥ p. - Since |xy| ≤ p, y = aᵏ with k ≥ 1.
- Pump i = 2:
xy²z = aᵖ⁺ᵏbᵖis not in L. - Contradiction, so L is not regular.
Practise this format on GGSIPU MCA important questions.
MCA-118 and the GGSIPU MCA Sem 2 papers it connects to
Full paper list: GGSIPU MCA syllabus.
The scheme pairs this elective with the MCA-168 Theory of Computations Lab (1 credit). This book covers the theory paper, but these sections feed the lab outcomes:
- Unit 1 JFLAP section (page 21) → lab CO1, finite machines in JFLAP.
- Unit 1 DFA and NFA designs (pages 7-12) → CO2 and CO4, recognisers and simulation.
- Unit 2 CFG table (page 25) → CO5, designing a CFG.
- Unit 2-3 PDA and TM models (pages 33-45) → CO3, abstract models.
Semester 2 core papers: MCA-102 Data and File Structures, MCA-104 Object Oriented Software Engineering and MCA-106 Python Programming.
The pre-requisite is MCA-101 Discrete Structures (Semester 1); Unit 4's P vs NP leads into MCA-201 Design and Analysis of Algorithms.
MCA-118 Theory of Computations notes FAQs
How do I get the full MCA-118 notes?
Send us a message on WhatsApp at 9899436384 using the "Get Full Notes" button on this page. The full MCA-118 notes come only as a printed book; they are not sold as a PDF. We confirm your order and address on WhatsApp, then dispatch the book. Delivery takes 5 to 7 days at most, and the exact time depends on your location.
Are the MCA-118 Theory of Computations notes available as a PDF?
No. The complete MCA-118 notes are available only as a printed book. The "View Sample PDF" button gives you seven watermarked pages (the cover, the index and one content page from each unit) so you can check the layout, diagrams and depth before ordering. The full 67-page content is never shared as a PDF.
What is the passing mark for MCA-118 Theory of Computations?
MCA-118 is marked out of 100: 40 internal and 60 end-term, where the end-term paper is 12 for Q1 plus 12 for each of the 4 units. The MCA scheme of examination states pass marks as 40 out of 100 marks for every paper. Rules on end-term minimums and re-appear are in GGSIPU Ordinance 11.
Is MCA-118 compulsory in GGSIPU MCA Semester 2?
No. MCA-118 is one of ten Core Elective I papers, and each student picks one. The scheme says an elective needs at least 20 students for classes; with fewer, it may still be offered, but students complete it through a MOOC platform such as SWAYAM with approval and then sit the institute's evaluation. Check with your institute which electives run for your batch.
Do the MCA-118 notes cover JFLAP?
Yes. Section 16 of Unit 1 (page 21) introduces JFLAP, the Java tool for automata. It lists what JFLAP can do and gives click-by-click steps to build and test a DFA, convert an NFA to a DFA, minimise the result and export it. JFLAP is named in the official MCA-118 Unit I syllabus and in the outcomes of the matching MCA-168 lab.
Which syllabus and batch do the MCA-118 notes follow?
They follow the GGSIPU MCA (2 years) scheme for affiliated institutes, effective from academic session 2025-26, approved by the USIC&T Board of Studies on 28 July 2025. All four units match the official MCA-118 topics. If your batch was admitted before 2025-26, compare your own syllabus copy with the table on this page before ordering.
Get the full MCA-118 Theory of Computations Notes on WhatsApp
The complete MCA-118 book of Theory of Computations notes in English is ordered on WhatsApp and delivered as a printed copy. It is not available as a PDF.
- Format: printed book, 67 pages, English; not available as PDF.
- Delivery: within 5 to 7 days at most; the exact time may vary with your location.
Order the printed MCA-118 notes book on WhatsApp (4 units, 67 pages)
Unnati Educations is an independent education provider based in Vikaspuri, Delhi. We are not affiliated with, authorised by, or endorsed by Guru Gobind Singh Indraprastha University (GGSIPU). 'GGSIPU' and 'IPU' are used only to describe the syllabus our notes follow. For official information, visit ipu.ac.in.
Ready for the full notes?
Discuss coverage and delivery with our team.