2021 question paper

FORMAL LANGUAGE & AUTOMATA THEORY

27 questions

1. Q1a. Which of the following statements is/are false? A. For every nondeterministic TM, an equivalent deterministic TM exists. B. Turing recognizable languages are closed under union and complementation. C. Turing decidable languages are closed under intersection and complementation. D. Turing recognizable languages are closed under union and intersection. (i) A and D only (ii) A and C only (iii) B only (iv) C only20212m

   Module 5: Undecidability

   Which of the following statements is/are false?

   A. For every nondeterministic TM, an equivalent deterministic TM exists.
   B. Turing recognizable languages are closed under union and complementation.
   C. Turing decidable languages are closed under intersection and complementation.
   D. Turing recognizable languages are closed under union and intersection.

   (i) A and D only
   (ii) A and C only
   (iii) B only
   (iv) C only

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (iii) B only

   Explanation

   Evaluate each statement:

   A. For every nondeterministic TM, an equivalent deterministic TM exists.

   True. Turing Machines are deterministic simulatable: a DTM can simulate an NTM via BFS over computation tree with at most exponential slowdown. NTM does not increase power, unlike for PDA. $NTM = DTM$ in language power.

   B. Turing-recognizable (RE) languages are closed under union and complementation.

   False.

   • RE is closed under union and intersection: if $M_1$ recognizes $L_1$ and $M_2$ recognizes $L_2$, a NTM can dovetail to recognize $L_1 \cup L_2$ and $L_1 \cap L_2$.
   • RE is NOT closed under complement. If $L$ is RE but not recursive, $\overline{L}$ is not RE. Example $A_{TM}$ is RE, $\overline{A_{TM}}$ is not RE. So the conjunction “union and complementation” fails.

   C. Turing-decidable (Recursive) languages are closed under intersection and complementation.

   True. Recursive languages are decidable by a TM that always halts. Deciders can be complemented by swapping accept/reject, and intersected via product construction. They are closed under all Boolean operations: union, intersection, complement, difference.

   D. Turing-recognizable languages are closed under union and intersection.

   True. As noted in B, RE retains closure under union and intersection, only complement fails.

   Summary

   Statement	Truth
   A	True
   B	False
   C	True
   D	True

   Only B is false.

   Final Answer

   B only is false → Option (iii).

2. Q1b. Enumerator in a Turing machine is a TM with: (i) an output printer (ii) 5 input tapes (iii) a stack (iv) None of the above20212m

   Module 4: Turing Machines (TM)

   Enumerator in a Turing machine is a TM with:

   (i) an output printer
   (ii) 5 input tapes
   (iii) a stack
   (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (i) an output printer

   Explanation

   An Enumerator $E$ is a variant of Turing Machine that enumerates a language.

   Formal definition (Sipser):

   Enumerator is a TM with a work tape and a write-only output tape (printer). The printer head moves only right and cannot read. Whenever $E$ wants to output a string, it writes it on the printer and the string is considered enumerated.

   • Enumerator has no input; it starts from blank tape.
   • Language enumerated is $L(E) = \{ w \mid E \text{ eventually prints } w \}$.
   • Theorem: $L$ is Turing-recognizable iff some enumerator enumerates $L$.

   Options:

   • (ii) 5 tapes — multi-tape TM, not enumerator.
   • (iii) stack — PDA, not enumerator.
   • Hence (i) is correct.

   Final Answer

   Enumerator = TM with an output printer → Option (i).

3. Q1c. The language: L = \{ a^m b^n c^{m+n} \mid m,n \ge 1 \} is: (i) regular (ii) context-free but not regular (iii) context-sensitive but not context-free (iv) type-0 but not context-sensitive20212m

   Module 3: Context-Sensitive Languages

   The language:

   $$L = \{ a^m b^n c^{m+n} \mid m,n \ge 1 \}$$

   is:

   (i) regular
   (ii) context-free but not regular
   (iii) context-sensitive but not context-free
   (iv) type-0 but not context-sensitive

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (ii) Context-free but not regular

   Explanation

   $L = \{ a^m b^n c^{m+n} \mid m,n \ge 1 \}$.

   Not Regular

   Use Pumping Lemma. Let $p$ be pumping length, $w = a^p b^p c^{2p} \in L$. Pumping $y$ in $a$ segment breaks $m+n$ balance.

   Context-Free

   PDA construction:

   1. Push $a$’s (m times) → stack $= A^m$.
   2. Push $b$’s (n times) → stack $= A^m B^n$ (or same symbol).
   3. For each $c$, pop one symbol. Accept if empty after $m+n$ $c$’s and no extra input.

   Alternatively grammar:
   $S \rightarrow a S c \mid a T c$
   $T \rightarrow b T c \mid b c$

   This generates $a^m b^n c^{m+n}$.

   Not context-sensitive requirement beyond; CFL suffices, but not regular. Not Type-0/1 only.

   Final Answer

   Context-free but not regular → Option (ii).

4. Q1d. The maximum number of states of a DFA converted from an NFA with n states is: (i) n (ii) n^2 (iii) 2^n (iv) None of the above20212m

   Module 1: Introduction & Regular Languages

   The maximum number of states of a DFA converted from an NFA with $n$ states is:

   (i) $n$
   (ii) $n^2$
   (iii) $2^n$
   (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (iii) $2^{n}$

   Explanation

   NFA with $n$ states → DFA via subset construction:

   Each DFA state is a subset of NFA states. NFA states set $Q_N$, $|Q_N|=n$.

   Number of distinct subsets = $|\mathcal{P}(Q_N)| = 2^{n}$.

   This includes $\emptyset$ (dead state).

   Hence DFA has at most $2^{n}$ states. Upper bound is tight: there exist NFA families (e.g., language “$n$th symbol from end is 1”) that require exactly $2^{n}$ DFA states.

   Final Answer

   Maximum $2^{n}$ states → Option (iii). (Minimal DFA may be smaller, but maximum is $2^{n}$.)

5. Q1e. If L_1 and L_2 are CFLs, L_1 - L_2 is ____ context-free. (i) always (ii) sometimes (iii) never (iv) None of the above20212m

   Module 2: Context-Free Languages (CFL) and PDA

   If $L_1$ and $L_2$ are CFLs, $L_1 - L_2$ is ____ context-free.

   (i) always
   (ii) sometimes
   (iii) never
   (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (ii) sometimes (i.e., not always — CFLs are not closed under difference)

   Explanation

   $L_1 - L_2 = L_1 \cap \overline{L_2}$.

   • CFLs are closed under union, concatenation, Kleene star, but NOT under intersection, complement, difference.
   • Since complement of a CFL is not necessarily CFL, difference need not be CFL.

   Counterexample:
   $L_1 = a^*b^*c^*$ (actually regular, also CFL)
   Let $L_1 = \{a^n b^n c^m\}$ (CFL) and $L_2 = \{a^m b^n c^n\}$ (CFL)
   $L_1 \cap L_2 = \{a^n b^n c^n\}$ not CFL.
   Then $L_1 - ( \Sigma^* - L_2)$ style constructions show difference can be non-CFL.

   But sometimes it is CFL: e.g., if $L_2$ is regular, then $L_1 - L_2 = L_1 \cap \overline{L_2}$ is CFL because CFL ∩ Regular = CFL. So difference is sometimes CFL.

   Many textbooks phrase options as:

   • (i) always — false
   • (ii) sometimes / not always closed
   • (iii) never — false (counterexample above shows sometimes)

   Hence correct is not necessarily CFL → Option (ii) sometimes (or “not always”). If exam key uses “never”, they mean “not closed”, also acceptable as (iii) in that phrasing — but strictly “sometimes” is precise.

   Final Answer

   $L_1 - L_2$ is not guaranteed CFL → Not closed → Option (ii) sometimes / not always (exam may list as (iii) never in weaker phrasing).

6. Q1f. Which of the following does not have left recursion? (i) Chomsky Normal Form (ii) Greibach Normal Form (iii) Backus–Naur Form (iv) All of the above20212m

   Module 2: Context-Free Languages (CFL) and PDA

   Which of the following does not have left recursion?

   (i) Chomsky Normal Form
   (ii) Greibach Normal Form
   (iii) Backus–Naur Form
   (iv) All of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (i) Chomsky Normal Form and (ii) Greibach Normal Form — both have no left recursion; if single choice required, (i) CNF is the textbook answer, and BNF may contain left recursion.

   Explanation

   Left recursion: Production $A \rightarrow A\alpha$.

   • Chomsky Normal Form (CNF): $A \rightarrow BC$ or $A \rightarrow a$, where $B,C\in V$, $a\in T$. No $A$ on RHS leftmost as non-terminal with same $A$, and no $A\rightarrow A\alpha$. No left recursion.
   • Greibach Normal Form (GNF): $A \rightarrow a\alpha$, where $a\in T$, $\alpha\in V^*$. Starts with terminal → no left recursion by definition.
   • Backus-Naur Form (BNF): General notation for CFG, e.g., $A ::= A + B \mid B$. May contain left recursion (common in expression grammars).

   Options:

   • (i) CNF → no left recursion ✓
   • (ii) GNF → no left recursion ✓
   • (iii) BNF → can have left recursion ✗
   • (iv) All of above → false because BNF can have it.

   If exam expects single answer, CNF (and GNF) are correct; many keys mark (i) Chomsky Normal Form.

   Final Answer

   CNF / GNF have no left recursion → Option (i) (and (ii)). BNF can have left recursion.

7. Q1g. For an NFA with n states, the minimized DFA has: (i) m \le 2^n (ii) n \le m (iii) one accept state (iv) m = 2^n20212m

   Module 1: Introduction & Regular Languages

   For an NFA with $n$ states, the minimized DFA has:

   (i) $m \le 2^n$
   (ii) $n \le m$
   (iii) one accept state
   (iv) $m = 2^n$

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (i) $m \le 2^{n}$

   Explanation

   Same as Q28 / Q87: Subset construction.

   NFA $n$ states → DFA has at most $2^{n}$ subsets. Minimized DFA $m$ ≤ subset DFA ≤ $2^{n}$.

   • (ii) $n \le m$ is not necessarily true (NFA can be smaller).
   • (iv) $m =2^{n}$ is not always (upper bound, but often smaller).
   • (iii) one accept state is false (can be multiple).

   Final Answer

   $m \le 2^{n}$ → Option (i).

8. Q1h. ____ is the acyclic graphical representation of a grammar. (i) Binary tree (ii) Octtree (iii) Parse tree (iv) None of the above20212m

   Module 2: Context-Free Languages (CFL) and PDA

   ____ is the acyclic graphical representation of a grammar.

   (i) Binary tree
   (ii) Octtree
   (iii) Parse tree
   (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (iii) Parse tree

   Explanation

   Parse tree (derivation tree / syntax tree): Acyclic, rooted, ordered tree representing derivation.

   • Root = start symbol $S$
   • Internal nodes = non-terminals
   • Leaves = terminals (yield = derived string)
   • No cycles (grammar is context-free, derivation finite).

   Not binary tree specifically (parse tree can be $n$-ary), not octtree. Binary tree is for CNF.

   Final Answer

   Parse tree → Option (iii).

9. Q1i. A minimum state DFA for the language: L = \{ w \in \{0,1\}^* : \#0(w) \equiv 0 \mod 3,\; \#1(w) \equiv 0 \mod 5 \} has: (i) 15 states (ii) 11 states (iii) 10 states (iv) 9 states20212m

   Module 1: Introduction & Regular Languages

   A minimum state DFA for the language:

   $$L = \{ w \in \{0,1\}^* : \#0(w) \equiv 0 \mod 3,\; \#1(w) \equiv 0 \mod 5 \}$$

   has:

   (i) 15 states
   (ii) 11 states
   (iii) 10 states
   (iv) 9 states

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (i) 15 states

   Explanation

   Language $L = \{ w \mid \#_0 \bmod 3 =0,\; \#_1 \bmod 5 =0\}$ is same as Q92 / Q112.

   As before: DFA for $\#_0 \bmod 3$ needs 3 states, for $\#_1 \bmod 5$ needs 5 states. Product → $3 \times 5 =15$ minimal states.

   Transitions: $15 \times 2 =30$.

   Other options 11,10,9 would be for different moduli (e.g., 3+5=8) — incorrect; must multiply, not add.

   Final Answer

   15 states → Option (i).

10. Q1j. The construction time for DFA from NFA with m nodes is: (i) O(m^2) (ii) O(2^m) (iii) O(m) (iv) O(\log m)20212m

    Module 1: Introduction & Regular Languages

    The construction time for DFA from NFA with $m$ nodes is:

    (i) $O(m^2)$
    (ii) $O(2^m)$
    (iii) $O(m)$
    (iv) $O(\log m)$

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer

    Correct Option: (ii) $O(2^{m})$

    Explanation

    NFA with $m$ states → DFA via subset construction:

    Number of DFA states $= 2^{m}$ in worst case, and constructing each state requires processing transitions for each symbol ($|\Sigma|$).

    Time is proportional to number of subsets times alphabet:

    $$T = O(|\Sigma| \cdot 2^{m}) = O(2^{m})$$

    (If counting edges, $O(m \cdot 2^{m})$ but dominant exponential.)

    Options:

    • $O(m^2)$ — polynomial, false for NFA→DFA
    • $O(m)$ — linear, false
    • $O(\log m)$ — false

    Final Answer

    $O(2^{m})$ → Option (ii).

11. Budget App•POCKETLY

    Pocketly on Android

    Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

    Install Pocketly
12. Q2a. Tabulate the Chomsky hierarchy of grammars with an example for each.20217m

    Module 1: Introduction & Regular Languages

    Tabulate the Chomsky hierarchy of grammars with an example for each.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer

    Chomsky Hierarchy of Grammars

    Type	Grammar Name	Production Form $\alpha \rightarrow \beta$	Language Class	Automaton
    Type-0	Unrestricted	No restriction on $\alpha,\beta$ (except $\alpha
    eq \epsilon$)	Recursively Enumerable (RE)	Turing Machine
    Type-1	Context-Sensitive	$|\alpha| \le |\beta|$, $\beta$ has $\alpha$ in context	Context-Sensitive (CSL)	Linear Bounded Automaton
    Type-2	Context-Free	$A \rightarrow \gamma$, $A \in V$, $\gamma \in (V \cup T)^*$	Context-Free (CFL)	Pushdown Automaton (PDA)
    Type-3	Regular / Right-Linear	$A \rightarrow aB \mid a$ (or left-linear)	Regular (REG)	Finite Automaton (DFA/NFA)

    Examples

    Type	Example Grammar	Language Generated
    Type-0	$S \rightarrow aSb \mid \epsilon$ with unrestricted rules e.g. $aB \rightarrow Ba$	$\{a^n b^n c^n \mid n\ge0\}$ or any computable language
    Type-1	$S \rightarrow aBC \mid aSBC$, $CB \rightarrow BC$, $aB \rightarrow ab$, $bB \rightarrow bb$, $bC \rightarrow bc$, $cC \rightarrow cc$	$\{a^n b^n c^n \mid n\ge1\}$
    Type-2	$S \rightarrow aSb \mid SS \mid \epsilon$	$\{w \mid \#_a(w) = \#_b(w)\}$ (balanced parentheses)
    Type-2	$S \rightarrow (S) \mid SS \mid \epsilon$	Balanced parentheses language
    Type-3	$S \rightarrow 0S \mid 1S \mid \epsilon$	$\{0,1\}^*$ (all binary strings)
    Type-3	$S \rightarrow aS \mid bA$, $A \rightarrow bA \mid b$	$\{a^m b^n \mid m,n\ge1\}$ (right-linear)

    Containment Relations

    $$\text{REG} \subset \text{DCFL} \subset \text{CFL} \subset \text{CSL} \subset \text{RE} \subset \text{ALL}$$

    Each level strictly contained in the next (proper subsets).

    Notes

    • Type-0 = RE = recognized by TM; not all decidable.
    • Type-1 = CSL = decided by LBA (PSPACE-complete membership).
    • Type-2 = CFL = parsed in $O(n^3)$ (CYK); inherently ambiguous CFLs exist.
    • Type-3 = REG = recognized by FA/DFA; all decidable properties.

    Final Answer

    Table above summarizes all four Chomsky types with production forms, language classes, automata, and concrete grammar examples.

13. Q2b. Design a finite-state machine (FSM) for a parity checker.20217m

    Module 1: Introduction & Regular Languages

    Design a finite-state machine (FSM) for a parity checker.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer

    Parity Checker FSM: Checks if number of 1s in input is even (even parity) or odd (odd parity). Common use: error detection in communication.

    Assumptions

    • Input alphabet: $\Sigma = \{0, 1\}$ (binary stream)
    • Output: Even (0) or Odd (1) parity bit after each input, or final parity at end
    • We present Moore and Mealy versions

    ---

    1. Moore Machine (Output on State)

    States: $Q = \{E, O\}$

    • $E$: Even number of 1's seen so far (initial, accepting for even parity)
    • $O$: Odd number of 1's seen so far

    Output function $\lambda$:

    • $\lambda(E) = 0$ (even parity)
    • $\lambda(O) = 1$ (odd parity)

    Transition function $\delta$:

    State	Input 0	Input 1
    $E$	$E$	$O$
    $O$	$O$	$E$

    State Diagram:

            0
         ┌────┐
         │    ▼
      (E)───►(O)
         ▲   │
         └───1
    

    • On 0: stay in same parity state
    • On 1: flip parity

    Formal Moore: $M = (Q, \Sigma, \Delta, \delta, \lambda, q_0)$

    • $Q = \{E, O\}$, $\Sigma = \{0,1\}$, $\Delta = \{0,1\}$
    • $\delta(E,0)=E, \delta(E,1)=O, \delta(O,0)=O, \delta(O,1)=E$
    • $\lambda(E)=0, \lambda(O)=1$
    • $q_0 = E$

    ---

    2. Mealy Machine (Output on Transition)

    States: $Q = \{E, O\}$ (same states, no output on states)

    Output on transition:

    Transition	Input	Next State	Output
    $E \xrightarrow{0} E$	0	$E$	0
    $E \xrightarrow{1} O$	1	$O$	1
    $O \xrightarrow{0} O$	0	$O$	1
    $O \xrightarrow{1} E$	1	$E$	0

    State Diagram:

          0/0
       ┌─────┐
       │     ▼
      (E)──►(O)
      │1/1   │0/1
       └─────1/0
    

    Formal Mealy: $M = (Q, \Sigma, \Delta, \delta, \lambda, q_0)$ with $\lambda: Q\times\Sigma \to \Delta$.

    ---

    3. Even Parity Generator (Output at End)

    If only final parity needed (not running):

    • Run Moore/Mealy above
    • After last input, output $\lambda(q)$ (Moore) or last transition output (Mealy)
    • Even parity = 0 if even # of 1's, 1 if odd

    Test Sequence

    Input	Moore State Seq	Moore Output Seq	Mealy Output Seq
    1011	$E \to O \to O \to E \to O$	0,1,1,1,0	1,1,1,0
    Even # 1s: 1100 → ends in E, output 0
    Odd # 1s: 110 → ends in O, output 1

    ---

    Final Answer

    Parity Checker FSM — 2-state Moore/Mealy machine tracking even/odd count of 1's.

    • Moore: Output = state parity (E→0, O→1)
    • Mealy: Output on each transition (flip on 1, hold on 0)
    • Transitions: 0 = stay, 1 = flip
    • Minimal: 2 states (even/odd are distinguishable)
14. Q3a. Construct an NFA accepting strings over \{0,1,2\} beginning with 0, followed by an odd number of 1s, ending with any number of 2s.20217m

    Module 1: Introduction & Regular Languages

    Construct an NFA accepting strings over $\{0,1,2\}$ beginning with 0, followed by an odd number of 1s, ending with any number of 2s.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer

    Language: $L = \{ 0\, 1^{2k+1}\, 2^* \mid k \ge 0 \} = \{ 01\, 2^*,\, 0111\, 2^*,\, 011111\, 2^*, \dots \}$

    Structure: starts with 0 → odd number of 1's → any number of 2's.

    ---

    NFA Design

    NFA: $N = (Q, \Sigma, \delta, q_0, F)$

    • $\Sigma = \{0,1,2\}$
    • $Q = \{q_0, q_1, q_2, q_3\}$
    • $q_0$ = start
    • $F = \{q_3\}$ (final)

    States meaning:

    • $q_0$: initial, expecting leading 0
    • $q_1$: saw 0, read first 1 (odd count = 1)
    • $q_2$: in even number of 1's (after 2nd, 4th, ...)
    • $q_3$: in odd number of 1's (after 1st, 3rd, ...) — can transition to 2's

    ---

    Transition Function $\delta$

    State	Input	Next State(s)
    $q_0$	$0$	$\{q_1\}$
    $q_1$	$1$	$\{q_2\}$
    $q_2$	$1$	$\{q_1\}$
    $q_1$	$2$	$\{q_3\}$
    $q_3$	$2$	$\{q_3\}$

    No other transitions (missing transitions = dead/implicit reject).

    ---

    State Diagram

           0
       ┌───────┐
       │       ▼
     (q0)──►(q1)──1──►(q2)
       │    ▲   │    │
       │    │   └────1
       │    2     │
       ▼    │     │
      (q3)◄──2─────┘
        2
    

    ---

    How It Works

    Input	Path	Accept?
    01	$q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_2$ → no (ends in $q_2$, even 1's)
    011	$q_0 \to q_1 \xrightarrow{1} q_2 \xrightarrow{1} q_1$ → yes ($q_1 \xrightarrow{2} q_3 \in F$)
    0111	$q_0 \to q_1 \xrightarrow{1} q_2 \xrightarrow{1} q_1 \xrightarrow{1} q_2$ → no (even)
    012	$q_0 \to q_1 \xrightarrow{1} q_2 \xrightarrow{2}$ → no ($q_2$ has no 2-transition)
    0112	$q_0 \to q_1 \xrightarrow{1} q_2 \xrightarrow{1} q_1 \xrightarrow{2} q_3$ → yes
    01112	$q_0 \to q_1 \xrightarrow{1} q_2 \xrightarrow{1} q_1 \xrightarrow{1} q_2 \xrightarrow{2}$ → no
    01122	$q_0 \to q_1 \xrightarrow{1} q_2 \xrightarrow{1} q_1 \xrightarrow{2} q_3 \xrightarrow{2} q_3$ → yes
    0	$q_0 \xrightarrow{0} q_1$ → no (no 1's, count=0 even)

    ---

    Equivalent DFA (via Subset Construction)

    States = subsets of NFA states:

    • $A = \{q_0\}$
    • $B = \{q_1\}$
    • $C = \{q_2\}$
    • $D = \{q_1, q_3\}$
    • $E = \{q_3\}$ (accepting)
    • Dead = $\emptyset$

    But NFA is simpler and sufficient.

    ---

    Regular Expression

    $0(11)^*1\,2^* = 0\,(11)^*\,1\,2^*$

    Verification:

    • 01 = $0 \cdot (11)^0 \cdot 1 \cdot 2^0$ ✓
    • 0111 = $0 \cdot (11)^1 \cdot 1$ ✓
    • 011122 = $0 \cdot (11)^1 \cdot 1 \cdot 2^2$ ✓

    ---

    Final Answer

    NFA with 4 states ($q_0,q_1,q_2,q_3$):

    • $q_0 \xrightarrow{0} q_1$ (leading 0)
    • $q_1 \xrightarrow{1} q_2 \xrightarrow{1} q_1$ (toggle odd/even 1's)
    • $q_1 \xrightarrow{2} q_3$ (odd 1's → can start 2's)
    • $q_3 \xrightarrow{2} q_3$ (any number of 2's)
    • Final = $\{q_3\}$
    • Accepts $0(11)^*1 2^*$ exactly.
15. Q3b. Construct a PDA that accepts: L = \{ u a w b : u,w \in \{a,b\}^*,\; |u| = |w| \}20217m

    Module 2: Context-Free Languages (CFL) and PDA

    Construct a PDA that accepts:

    $$L = \{ u a w b : u,w \in \{a,b\}^*,\; |u| = |w| \}$$

    View this question on its own page →

    CopySearch GoogleAsk AI
16. Q4a. Design a Turing Machine to compute n \bmod 2.20217m

    Module 4: Turing Machines (TM)

    Design a Turing Machine to compute $n \bmod 2$.

    View this question on its own page →

    CopySearch GoogleAsk AI
17. Q4b. Design a DFA for the regular expression: 1^*(10)^*20217m

    Module 1: Introduction & Regular Languages

    Design a DFA for the regular expression:

    $$1^*(10)^*$$

    View this question on its own page →

    CopySearch GoogleAsk AI
18. Q5a. Using the CYK algorithm, determine whether baaba is in L(G) for the grammar: `` S → AB | BC A → BA | a B → CC | b C → AB | a ``202114m

    Module 2: Context-Free Languages (CFL) and PDA

    Using the CYK algorithm, determine whether baaba is in $L(G)$ for the grammar:

    S → AB | BC
    A → BA | a
    B → CC | b
    C → AB | a
    

    View this question on its own page →

    CopySearch GoogleAsk AI
19. Q5b. Suppose L is CFL and R is regular: (i) Is L - R always CFL? (ii) Is R - L always CFL?202114m

    Module 2: Context-Free Languages (CFL) and PDA

    Suppose $L$ is CFL and $R$ is regular:

    (i) Is $L - R$ always CFL?
    (ii) Is $R - L$ always CFL?

    View this question on its own page →

    CopySearch GoogleAsk AI
20. Q6a. Show that the language: L = \{ a^{n!} : n \ge 0 \} is not regular or not context-free.20217m

    Module 1: Introduction & Regular Languages

    Show that the language:

    $$L = \{ a^{n!} : n \ge 0 \}$$

    is not regular or not context-free.

    View this question on its own page →

    CopySearch GoogleAsk AI
21. Q6b. Let G be a CFG in CNF with b variables. Show that if G derives any string using at least 2^b steps, then L(G) is infinite.20217m

    Module 2: Context-Free Languages (CFL) and PDA

    Let $G$ be a CFG in CNF with $b$ variables. Show that if $G$ derives any string using at least $2^b$ steps, then $L(G)$ is infinite.

    View this question on its own page →

    CopySearch GoogleAsk AI
22. Budget App•POCKETLY

    Pocketly on Android

    Log daily food, travel, and hostel expenses instantly. Set monthly spending limits and see where your money goes without complex spreadsheets.

    Install Pocketly
23. Q7a. State and prove the pumping lemma for regular languages.20217m

    Module 1: Introduction & Regular Languages

    State and prove the pumping lemma for regular languages.

    View this question on its own page →

    CopySearch GoogleAsk AI
24. Q7b. Check whether the grammar: S \to aSa \mid bSb \mid a \mid b is ambiguous.20217m

    Module 2: Context-Free Languages (CFL) and PDA

    Check whether the grammar:

    $$S \to aSa \mid bSb \mid a \mid b$$

    is ambiguous.

    View this question on its own page →

    CopySearch GoogleAsk AI
25. Q8a. Show that the function: f(x,y) = x + y is primitive recursive.20217m

    Module 5: Undecidability

    Show that the function:

    $$f(x,y) = x + y$$

    is primitive recursive.

    View this question on its own page →

    CopySearch GoogleAsk AI
26. Q8b. Construct a PDA accepting: L = \{ a^{2n}bc : n \ge 0 \}20217m

    Module 2: Context-Free Languages (CFL) and PDA

    Construct a PDA accepting:

    $$L = \{ a^{2n}bc : n \ge 0 \}$$

    View this question on its own page →

    CopySearch GoogleAsk AI
27. Q9a. Write a short note on the Post Correspondence Problem.20213.5m

    Module 5: Undecidability

    Write a short note on the Post Correspondence Problem.

    View this question on its own page →

    CopySearch GoogleAsk AI
28. Q9b. Write a short note on Chomsky Normal Form.20213.5m

    Module 2: Context-Free Languages (CFL) and PDA

    Write a short note on Chomsky Normal Form.

    View this question on its own page →

    CopySearch GoogleAsk AI
29. Q9d. Write a short note on the Pumping Lemma for CFL.20213.5m

    Module 2: Context-Free Languages (CFL) and PDA

    Write a short note on the Pumping Lemma for CFL.

    View this question on its own page →

    CopySearch GoogleAsk AI