GATE CS & IT Engineering Theory of Computation Syllabus

Theory of Computation syllabus — full chapter and topic list

Expand any chapter to see its topics and sub-topics. This is the whole examinable outline for Theory of Computation in GATE CS & IT Engineering, not a summary of it.

1. 1

   Regular expressions and finite automata

   2 topics

   • Regular expressions
   • Finite automata
2. 2

   Context-free grammars and push-down automata

   2 topics

   • Context-free grammars
   • Push-down automata
3. 3

   Regular and context-free languages, pumping lemma

   3 topics

   • Regular languages
   • Context-free languages
   • Pumping lemma
4. 4

   Turing machines and undecidability

   2 topics

   • Turing machines
   • Undecidability

Theory of Computation flashcards for GATE CS & IT Engineering

18 of 50 cards from the Theory of Computation deck — real questions with worked answers.

1. In the Chomsky hierarchy, list the four grammar types and the machine that recognizes each.

   Type 0 (unrestricted) — Turing machine; Type 1 (context-sensitive) — linear bounded automaton; Type 2 (context-free) — pushdown automaton; Type 3 (regular) — finite automaton.

2. Define a Deterministic Finite Automaton (DFA) as a 5-tuple.

   A DFA is $M = (Q, \Sigma, \delta, q_0, F)$ where $Q$ is a finite set of states, $\Sigma$ the input alphabet, $\delta: Q \times \Sigma \to Q$ the transition function, $q_0 \in Q$ the start state, and $F \subseteq Q$ the set of accepting states.

3. How does the transition function of an NFA differ from that of a DFA?

   An NFA's transition function maps to a set of states: $\delta: Q \times (\Sigma \cup \{\epsilon\}) \to 2^{Q}$, allowing multiple (or zero) next states and $\epsilon$-moves, whereas a DFA's is $\delta: Q \times \Sigma \to Q$ (exactly one next state).

4. If an NFA has $n$ states, what is the maximum number of states in the equivalent DFA obtained by subset construction?

   $2^{n}$ states, since each DFA state corresponds to a subset of the NFA's states.

5. Are DFAs and NFAs equivalent in language-recognizing power?

   Yes. Both recognize exactly the class of regular languages; every NFA can be converted to an equivalent DFA via subset construction.

6. State the three base cases in the definition of a regular expression over alphabet $\Sigma$.

   $\emptyset$ is a regex denoting the empty language; $\epsilon$ is a regex denoting $\{\epsilon\}$; for each $a \in \Sigma$, $a$ is a regex denoting $\{a\}$.

7. What are the three operations used to build regular expressions, in order of precedence?

   Kleene star (highest), then concatenation, then union/alternation $+$ (lowest). Parentheses override precedence.

8. What does Kleene's theorem state?

   A language is regular if and only if it can be described by a regular expression; equivalently, regular expressions and finite automata describe exactly the same class of languages.

9. Define the Kleene star $L^{*}$ of a language $L$.

   $L^{*} = \bigcup_{i=0}^{\infty} L^{i}$ where $L^{0} = \{\epsilon\}$ and $L^{i} = L \cdot L^{i-1}$. It is the set of all strings formed by concatenating zero or more strings from $L$.

10. Which closure operations are the regular languages closed under?

    Union, intersection, complement, concatenation, Kleene star, reversal, difference, and homomorphism — regular languages are closed under all of these.

11. State the regular-language pumping lemma.

    For every regular language $L$ there is a pumping length $p$ such that any string $w \in L$ with $|w| \geq p$ can be written as $w = xyz$ with $|xy| \leq p$, $|y| \geq 1$, and $xy^{i}z \in L$ for all $i \geq 0$.

12. How is the pumping lemma used to prove a language is NOT regular?

    Assume $L$ is regular with pumping length $p$, pick a string $w \in L$ with $|w| \geq p$, and show that for every valid decomposition $w = xyz$ there exists some $i$ with $xy^{i}z \notin L$, contradicting the lemma.

13. Show why $L = \{a^{n}b^{n} : n \geq 0\}$ is not regular using the pumping lemma idea.

    Pick $w = a^{p}b^{p}$. Since $|xy| \leq p$, $y$ consists only of $a$'s; pumping to $xy^{2}z$ gives more $a$'s than $b$'s, so $xy^{2}z \notin L$. Hence $L$ is not regular.

14. What is the role of the Myhill-Nerode theorem?

    A language $L$ is regular iff the number of equivalence classes of its right-invariant relation (Myhill-Nerode relation) is finite; that finite index equals the number of states in the minimal DFA.

15. What does DFA minimization produce, and is it unique?

    It produces the unique (up to isomorphism) DFA with the fewest states recognizing the same language, obtained by merging indistinguishable (equivalent) states.

16. Define a context-free grammar (CFG) as a 4-tuple.

    A CFG is $G = (V, \Sigma, R, S)$ where $V$ is the set of variables (non-terminals), $\Sigma$ the terminals, $R$ a finite set of production rules of the form $A \to \gamma$ with $A \in V$ and $\gamma \in (V \cup \Sigma)^{*}$, and $S \in V$ the start symbol.

17. What is the form of productions in Chomsky Normal Form (CNF)?

    Every rule is either $A \to BC$ (two variables) or $A \to a$ (single terminal); $S \to \epsilon$ is allowed only if $\epsilon$ is in the language. No other rule forms are permitted.

18. What is the form of productions in Greibach Normal Form (GNF)?

    Every production has the form $A \to a\alpha$ where $a$ is a terminal and $\alpha \in V^{*}$ is a (possibly empty) string of variables.

See more Theory of Computation flashcards →

Planning Theory of Computation for GATE CS & IT Engineering

Theory of Computation (GATE CS & IT Engineering) FAQ