2023 question paper

FORMAL LANGUAGE & AUTOMATA THEORY

28 questions

1. Q1a. A language accepted by deterministic pushdown automata is closed under which of the following? (i) Complement (ii) Union (iii) Both (i) and (ii) (iv) None of the above20232m

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

   A language accepted by deterministic pushdown automata is closed under which of the following?

   (i) Complement
   (ii) Union
   (iii) Both (i) and (ii)
   (iv) None of the above

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (i) Complement

   Explanation

   Languages accepted by Deterministic Pushdown Automata (DPDA) are Deterministic Context-Free Languages (DCFLs).

   Closure Properties of DCFLs

   Operation	Closed?
   Complement	Yes
   Union	No
   Intersection	No
   Intersection with Regular	Yes
   Concatenation	No
   Kleene Star	No

   Reason:

   • A DPDA can be complemented by swapping final/non-final states after ensuring it is total and handles end-of-input deterministically, similar to DFA complementation, but adapted for stack handling.
   • DCFLs are not closed under union: e.g., $L_1 = \{a^n b^n \mid n\ge0\}$ and $L_2 = \{a^n b^{2n} \mid n\ge0\}$ are DCFLs, but $L_1 \cup L_2$ is not a DCFL.
   • Since union fails, (iii) Both is false and (iv) is false.

   Contrast with general CFLs (NPDA)

   CFLs (non-deterministic) are not closed under complement nor intersection, but are closed under union, concatenation, Kleene star – opposite behaviour.

   Final Answer

   DCFL is closed under complement only. Hence option (i) Complement is correct.

2. Q1b. Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following is necessarily true? (i) m \le 2^n (ii) n \le m (iii) M has one accept state (iv) m = 2^n20232m

   Module 1: Introduction & Regular Languages

   Let $N$ be an NFA with $n$ states and let $M$ be the minimized DFA with $m$ states recognizing the same language. Which of the following is necessarily true?

   (i) $m \le 2^n$
   (ii) $n \le m$
   (iii) $M$ has 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

   NFA → DFA subset construction:

   • Each DFA state corresponds to a subset of NFA states.
   • With $n$ NFA states, there are at most $2^{n}$ subsets.
   • Hence the DFA obtained (before minimization) has $\le 2^{n}$ states.
   • Minimized DFA $M$ has $m \le$ number of subset-construction DFA states $\le 2^{n}$.

   So (i) is always true.

   Other options:

   • (ii) $n \le m$ is false: NFA can be exponentially smaller (e.g., language of $n^{th}$ from end needs $n+1$ NFA states but $2^{n}$ DFA states → $n < m$ sometimes, but not necessarily; sometimes DFA is smaller).
   • The converse $m \ge n$ is not guaranteed.

   Final Answer

   $m \le 2^{n}$ → Option (i). (Minimized DFA minimal, so $m$ is even tighter, but certainly $\le 2^{n}$.)

3. Q1c. A minimum state deterministic FA accepting the language: L = \{ w \mid w \in \{0,1\}^* \} where the number of 0's and 1's in w are divisible by 3 and 5 respectively, has: (i) 15 states (ii) 11 states (iii) 10 states (iv) 9 states20232m

   Module 1: Introduction & Regular Languages

   A minimum state deterministic FA accepting the language:

   $$L = \{ w \mid w \in \{0,1\}^* \}$$

   where the number of 0's and 1's in $w$ are divisible by 3 and 5 respectively, 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 (Other options typically include 8, etc., correct is 15)

   Explanation

   Language $L = \{ w \in \{0,1\}^* \mid \#_0(w) \bmod 3 =0 \;\land\; \#_1(w) \bmod 5 =0 \}$.

   This is intersection of two regular languages:

   • $L_0 = \{ w \mid \#_0(w) \equiv 0 \pmod 3 \}$ → DFA with 3 states ($r_0=0,1,2$).
   • $L_1 = \{ w \mid \#_1(w) \equiv 0 \pmod 5 \}$ → DFA with 5 states ($s_0=0..4$).

   Intersection via product construction: states = $Q_0 \times Q_1$ → $3 \times 5 =15$ states.

   Transitions: $\delta((r,s),0) = ((r+1)\bmod 3, s)$, $\delta((r,s),1) = (r, (s+1)\bmod5)$.

   Initial $(0,0)$, accepting $(0,0)$ only. Minimal because all pairs distinguishable (Myhill-Nerode: $(i,j)
   ot\equiv (i',j')$if$i
   eq i'$or$j
   eq j'$).

   Final Answer

   15 states (product DFA, minimal).

4. Q1d. The language \{ a^n b^n c^{n+m} \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-sensitive20232m

   Module 3: Context-Sensitive Languages

   The language $\{ a^n b^n c^{n+m} \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: (iii) Context-sensitive but not context-free (and hence not regular)

   Explanation

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

   Not Context-Free

   Assume $L$ is CFL, let $p$ be pumping length. Take $w = a^p b^p c^{p+1} \in L$ ($n=p, m=1$). By pumping lemma for CFL, $w = uvxyz$ with $|vxy|\le p$, $|vy|>0$. Pumping must stay within first $p$ $a$'s or $b$'s or $c$'s. Any pumping changes counts and breaks condition $\#_c > \#_a = \#_b$ (or breaks $a^n b^n$). Formal proof shows $L$ not CFL. Equivalent to $a^n b^n c^n$ (which is not CFL) with extra $c^m$ tail; intersection with regular $a^*b^*c^*$ does not help but $L \cap a^*b^*c^p$ style shows non-CFL.

   Context-Sensitive

   It is accepted by Linear Bounded Automaton. Grammar is context-sensitive:

   $S \rightarrow a S B C \mid a B C$
   $CB \rightarrow BC$
   $a B \rightarrow a b$
   $b B \rightarrow b b$
   $b C \rightarrow b c$
   $c C \rightarrow c c$

   This is Type-1 (CSG) but not Type-2. It is decidable but not CFL.

   Final Answer

   CSL but not CFL → Option (iii). Also not regular; ultimately Type-1 in Chomsky hierarchy.

5. Q1e. The string 1101 does not belong to the set represented by: (i) 1^* 0^* (0+1) (ii) 1(0+1)^*101 (iii) (1(0)^*(0+1)^*(0+1))^* (iv) \{00 + (11)^*0\}^*20232m

   Module 1: Introduction & Regular Languages

   The string $1101$ does not belong to the set represented by:

   (i) $1^* 0^* (0+1)$
   (ii) $1(0+1)^*101$
   (iii) $(1(0)^*(0+1)^*(0+1))^*$
   (iv) $\{00 + (11)^*0\}^*$

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (iv) $\{00 + (11)^*0\}^*$

   Explanation

   Test $w=1101$ against each regex:

   (i) $1^*0^*(0+1)$: = $1^*$ then $0^*$ then single $0$ or $1$. $1101 = \underbrace{11}_{1^*} \underbrace{0}_{0^*} \underbrace{1}_{(0+1)}$ → belongs.

   (ii) $1(0+1)^*101$: Must start with $1$ and end with $101$. $1101 = 1 \underbrace{1}_{(0+1)^*}101$? Actually $1101$ = $1$ + $\epsilon$ + $101$ with middle $1$? $1(0+1)^*101 = 1\,x\,101$ where $x=0$? For $w=1101$, $x=0$? Wait $1+0+101 =1101$ exactly, so $w = 1\cdot0\cdot101$? No $1\cdot101 =1101$ with $x=\epsilon$? $1(0+1)^* =1$, remaining $101 =101$ → $1101$ → belongs.

   (iii) $(1(0)^*(0+1)^*(0+1))^*$: This is essentially $\Sigma^*$ variant (can generate any string) → belongs.

   (iv) $\{00 + (11)^*0\}^*$: Generators: $00$ (ends 0) and $(11)^*0$ = even 1's followed by 0, also ends 0. Any concatenation of blocks ending in 0 always ends in 0. $1101$ ends in 1 → does not belong.

   Final Answer

   $1101
   otin {00 + (11)^0}^$ → Option (iv).

6. Q1f. A given grammar is called ambiguous if: (i) two or more productions have the same non-terminal on LHS (ii) a derivation tree has more than one associated sentence (iii) there exists a sentence with more than one derivation tree (iv) brackets are not present in the grammar20232m

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

   A given grammar is called ambiguous if:

   (i) two or more productions have the same non-terminal on LHS
   (ii) a derivation tree has more than one associated sentence
   (iii) there exists a sentence with more than one derivation tree
   (iv) brackets are not present in the grammar

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (iii) there exists a sentence with more than one derivation tree

   Explanation

   Ambiguous Grammar: Grammar $G$ is ambiguous iff there exists a string $w \in L(G)$ that has two or more distinct derivation trees (or equivalently two distinct leftmost / rightmost derivations).

   • (i) “two productions have same LHS” → false; e.g., $S \rightarrow a \mid b$ has same LHS but not ambiguous (each string one tree).
   • (ii) “derivation tree has more than one sentence” — every tree yields exactly one sentence (its yield), false.
   • (iii) True — definition of ambiguity: $\exists w: |\{ \text{parse trees for }w\}| \ge 2$.
   • (iv) “brackets not present” — irrelevant.

   Example ambiguous: $S \rightarrow S+S \mid S*S \mid a$; string $a+a*a$ has two trees (different precedence).

   Final Answer

   Ambiguous iff some sentence has ≥2 parse trees → Option (iii).

7. Q1g. Which one of the following statements is true? (i) The intersection of two CFLs is context-free (ii) Every CFL can be accepted by a DPDA (iii) The union of two CFLs is context-free (iv) The complement of a CFL is context-free20232m

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

   Which one of the following statements is true?

   (i) The intersection of two CFLs is context-free
   (ii) Every CFL can be accepted by a DPDA
   (iii) The union of two CFLs is context-free
   (iv) The complement of a CFL is context-free

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (iii) The union of two CFLs is context-free

   Explanation

   CFL closure:

   Operation	Closed?	Example
   Union $L_1 \cup L_2$	Yes	$S \rightarrow S_1 \mid S_2$
   Intersection $L_1 \cap L_2$	No	$a^n b^n c^* \cap a^* b^n c^n = a^n b^n c^n$ not CFL
   Complement	No	Follows from De Morgan
   Every CFL is DPDA	No	$\{a^n b^n\} \cup \{a^n b^{2n}\}$ is CFL but not DCFL
   Intersection of 2 CFLs is CFL	No

   Thus only union is guaranteed.

   Options:

   • (i) Intersection → false
   • (ii) Every CFL is DPDA → false (DCFL ⊂ CFL)
   • (iii) Union → true ✓
   • (iv) Complement → false

   Final Answer

   Union of two CFLs is CFL → Option (iii).

8. Q1h. From the options, the pair having different expressive powers is: (i) DPDA and NPDA (ii) DFA and NFA (iii) single-tape TM and multi-tape TM (iv) deterministic single-tape TM and nondeterministic single-tape TM20232m

   Module 4: Turing Machines (TM)

   From the options, the pair having different expressive powers is:

   (i) DPDA and NPDA
   (ii) DFA and NFA
   (iii) single-tape TM and multi-tape TM
   (iv) deterministic single-tape TM and nondeterministic single-tape TM

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (i) DPDA and NPDA

   Explanation

   Expressive power comparison:

   Pair	Power Same?
   DPDA vs NPDA	Different — NPDA = CFL, DPDA = DCFL ⊂ CFL. Example $\{a^n b^n\}\cup\{a^n b^{2n}\}$ is CFL but not DCFL.
   DFA vs NFA	Same — both = Regular
   Single-tape TM vs Multi-tape TM	Same — both = RE, polytime difference only
   Deterministic single-tape TM vs Nondeterministic single-tape TM	Same — $DTM = NTM$ in power

   Hence different expressive powers is DPDA vs NPDA.

   Final Answer

   DPDA and NPDA have different power → Option (i).

9. Q1i. Recursive languages are: (i) a proper superset of CFLs (ii) always recognizable (iii) also called type-0 languages (iv) recognizable by Turing machines20232m

   Module 4: Turing Machines (TM)

   Recursive languages are:

   (i) a proper superset of CFLs
   (ii) always recognizable
   (iii) also called type-0 languages
   (iv) recognizable by Turing machines

   View this question on its own page →

   CopySearch GoogleAsk AI

   Worked Solution

   Answer

   Correct Option: (i) a proper superset of CFLs (and (ii)/(iv) also true depending on option set)

   Explanation

   Recursive languages = Decidable languages = $L$ decided by TM that always halts.

   Hierarchy:
   $$\text{Regular} \subset \text{DCFL} \subset \text{CFL} \subset \text{CSL} \subset \text{Recursive} \subset \text{RE}$$

   • (i) Proper superset of CFLs → True. Every CFL is recursive (PDA can be simulated by halting TM), but not vice versa (e.g., $a^n b^n c^n$ is recursive not CFL).
   • (ii) Always recognizable (RE) → True, recursive ⊂ RE, so yes.
   • (iv) Recognizable by TM → True (RE definition).
   • (iii) also called Type-0 → False, Type-0 = RE, not Recursive (Type-1 is CSL, not Recursive either; Recursive is not a Chomsky type but decidable).

   If single choice, (i) proper superset of CFLs is the intended answer. If multiple, (i),(ii),(iv) are true.

   Final Answer

   Recursive languages are proper superset of CFLs → Option (i) (also RE).

10. Q1j. If P and Q are regular expressions (P is not null), then R = Q + RP has the unique solution: (i) R = QP (ii) R = PQ^* (iii) R = QP^* (iv) R = QP^*20232m

    Module 1: Introduction & Regular Languages

    If $P$ and $Q$ are regular expressions ($P$ is not null), then $R = Q + RP$ has the unique solution:

    (i) $R = QP$
    (ii) $R = PQ^*$
    (iii) $R = QP^*$
    (iv) $R = QP^*$

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer

    Correct Option: (iii) $R = QP^*$ (Arden’s Theorem)

    Explanation

    Arden’s Theorem: If $P$ does not contain $\epsilon$, then equation $R = Q + RP$ has unique solution $R = QP^*$.

    Proof: $R = Q + (Q + RP)P = Q(\epsilon + P) + RP^2 = \dots = Q(\epsilon + P + P^2 + \dots + P^{k}) + RP^{k+1}$. As $k \to \infty$, $RP^{k+1}$ contributes no finite strings if language, so $R = QP^*$.

    • (i) $QP$ missing star → incomplete.
    • (ii) $PQ^*$ swaps order (concatenation not commutative).
    • (iv) duplicate of (iii).

    Condition: $P$ not null ($\epsilon
    otin P$) ensures uniqueness.

    Final Answer

    $R = QP^*$ → Option (iii) (also (iv) if duplicate).

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. Discuss the Chomsky hierarchy of grammars with suitable examples.20237m

    Module 1: Introduction & Regular Languages

    Discuss the Chomsky hierarchy of grammars with suitable examples.

    View this question on its own page →

    CopySearch GoogleAsk AI
13. Q2b. State the pumping lemma for context-free languages.20237m

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

    State the pumping lemma for context-free languages.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer

    Pumping Lemma for Context-Free Languages (CFL)

    Statement:
    Let $L$ be a context-free language. Then there exists a constant $p \ge 1$ (the pumping length) such that for every string $w \in L$ with $|w| \ge p$, $w$ can be written as

    $$w = uvxyz$$

    satisfying the following conditions:

    1. $|vxy| \le p$ — the middle part $vxy$ is short (bounded by $p$)
    2. $|vy| \ge 1$ — at least one of $v$ or $y$ is non-empty (not both empty)
    3. For all $i \ge 0$: $uv^i x y^i z \in L$ — pumping $v$ and $y$ together (0, 1, 2, … times) keeps the string in $L$

    ---

    Interpretation

    • For any sufficiently long CFL string, you can find a decomposition into 5 parts such that the inner $v$ and $y$ can be "pumped" simultaneously (repeated same number of times) and the result stays in the language.
    • The simultaneous pumping of $v$ and $y$ is the key difference from the regular pumping lemma (which pumps a single $y$).
    • $|vxy| \le p$ means the "pumpable" region is near the center of the string (within length $p$).

    ---

    How to Use (Proving Non-CFL)

    To prove $L$ is not context-free:

    1. Assume $L$ is CFL → pumping lemma holds with some $p$.
    2. Choose a specific string $w \in L$ with $|w| \ge p$ (usually $w = a^p b^p c^p$ or similar).
    3. Show that for every valid decomposition $w = uvxyz$ satisfying (1) and (2), there exists some $i$ such that $uv^i x y^i z
       otin L$.
    4. Contradiction → $L$ not CFL.

    Common Strategy: Choose $w$ so that any $vxy$ of length $\le p$ cannot span all "coordinated" parts (e.g., three blocks $a^p b^p c^p$). Pumping disrupts the balance.

    ---

    Example Application

    Prove $L = \{a^n b^n c^n \mid n \ge 0\}$ is not CFL.

    1. Let $p$ be pumping length. Take $w = a^p b^p c^p \in L$, $|w| = 3p \ge p$.
    2. By lemma, $w = uvxyz$ with $|vxy| \le p$, $|vy| \ge 1$.
    3. Since $|vxy| \le p$, the substring $vxy$ cannot contain $a$'s, $b$'s, and $c$'s simultaneously — it lies within at most two adjacent blocks.
    4. Cases:
       • $vxy$ only in $a$'s: pumping adds $a$'s → $#a
         eq #b = #c$ ❌
       • $vxy$ only in $b$'s: pumping adds $b$'s → $#b
         eq #a, #c$ ❌
       • $vxy$ only in $c$'s: pumping adds $c$'s ❌
       • $vxy$ spans $a^p b^p$ boundary: pumping changes $\#a$ and $\#b$ differently (or adds both) → $#a
         eq #b$or$#b
         eq #c$ ❌
       • $vxy$ spans $b^p c^p$ boundary: similar ❌
    5. All decompositions fail for some $i
       e 1$. Contradiction.

    ---

    Contrast with Regular Pumping Lemma

    Aspect	Regular (Type-3)	CFL (Type-2)
    String split	$w = xyz$	$w = uvxyz$
    Pumped part	$y$ (single)	$v$ and $y$ (pair)
    Constraint	$|xy| \le p$	$|vxy| \le p$
    Non-empty	$|y| \ge 1$	$|vy| \ge 1$
    Result	$xy^i z \in L$	$uv^i x y^i z \in L$

    ---

    Important Notes

    • The lemma gives necessary but not sufficient condition for CFL.
    • There are non-CFL languages that satisfy the lemma (e.g., some non-context-free languages still pump).
    • For CFL, pumping is simultaneous of two substrings ($v$ and $y$), reflecting stack push/pop pairing.
    • The pumping length $p$ depends on the grammar (e.g., number of variables in Chomsky Normal Form).

    ---

    Final Answer

    Pumping Lemma for CFL: $\exists p \ge 1$ such that $\forall w \in L, |w| \ge p$, $w = uvxyz$ with $|vxy| \le p$, $|vy| \ge 1$, and $\forall i \ge 0, uv^i x y^i z \in L$. Used to prove languages like $\{a^n b^n c^n\}$ are not context-free.

14. Q3a. Design a PDA (empty stack and final state both) for L = \{ WW^r \mid W \in \{a,b\}^* \}.20237m

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

    Design a PDA (empty stack and final state both) for $L = \{ WW^r \mid W \in \{a,b\}^* \}$.

    View this question on its own page →

    CopySearch GoogleAsk AI

    Worked Solution

    Answer

    Language: $L = \{ W W^r \mid W \in \{a,b\}^* \}$ — even-length palindromes over $\{a,b\}$.

    $W^r$ = reverse of $W$. Examples: $\epsilon$, $aa$, $bb$, $abba$, $baab$, $aabbaa$, …

    ---

    PDA Design (NPDA)

    This language is not deterministic (NPDA needed) — the PDA must guess the midpoint.

    PDA: $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$

    • $Q = \{q_0, q_1, q_2\}$
      • $q_0$: reading first half, pushing symbols
      • $q_1$: reading second half, popping & matching
      • $q_2$: accept (final state)
    • $\Sigma = \{a, b\}$
    • $\Gamma = \{a, b, Z_0\}$ ($Z_0$ = bottom marker)
    • $q_0$ = start
    • $F = \{q_2\}$ (final state)
    • Empty stack also accepted: $Z_0$ remains at bottom, all input symbols pushed then popped

    ---

    Transition Function $\delta$

    Current State	Input	Stack Top	Action	Next State	Push/Pop
    $q_0$	$a$	$X \in \{a,b,Z_0\}$	Push $a$	$q_0$	$a$
    $q_0$	$b$	$X$	Push $b$	$q_0$	$b$
    $q_0$	$\epsilon$	$X$	Guess midpoint, switch to pop	$q_1$	$\epsilon$ (no change)
    $q_1$	$a$	$a$	Pop & match	$q_1$	$\epsilon$ (pop)
    $q_1$	$b$	$b$	Pop & match	$q_1$	$\epsilon$ (pop)
    $q_1$	$\epsilon$	$Z_0$	All matched, stack = $Z_0$	$q_2$	$\epsilon$

    Formally:

    • $\delta(q_0, a, X) = \{(q_0, aX)\}$ for $X \in \{a,b,Z_0\}$
    • $\delta(q_0, b, X) = \{(q_0, bX)\}$ for $X \in \{a,b,Z_0\}$
    • $\delta(q_0, \epsilon, X) = \{(q_1, X)\}$ for $X \in \{a,b,Z_0\}$ (midpoint guess)
    • $\delta(q_1, a, a) = \{(q_1, \epsilon)\}$
    • $\delta(q_1, b, b) = \{(q_1, \epsilon)\}$
    • $\delta(q_1, \epsilon, Z_0) = \{(q_2, \epsilon)\}$

    ---

    State Diagram

             a,b / X → aX,bX
          ┌───────────────────┐
          ▼                   │
      (q0)──ϵ, X/X──►(q1)──a/a:pop,b/b:pop──►(q1)
          │               │
          │               ϵ, Z0/ϵ
          │               ▼
          └──────────────►(q2)  [Accept]
    

    ---

    How It Works (Example: $W=ab$ → $abba$)

    1. Push phase ($q_0$):

       • Read a, push a: stack = a Z0
       • Read b, push b: stack = b a Z0
       • Guess midpoint ($\epsilon$): go to $q_1$, stack unchanged b a Z0

    2. Pop phase ($q_1$):

       • Read b, top=b → pop → stack = a Z0
       • Read a, top=a → pop → stack = Z0
       • Input exhausted, $\epsilon$-transition on $Z_0$ → $q_2$

    3. Accept: $q_2 \in F$, or stack = $Z_0$ (empty-stack acceptance).

    ---

    Acceptance Modes

    Mode	Condition
    Final State	Reach $q_2 \in F$
    Empty Stack	After reading all input, stack = $Z_0$ (all pushed symbols matched and popped, only $Z_0$ remains)

    Both equivalent here; PDA accepts by both.

    ---

    Why Nondeterministic?

    • The $\epsilon$-transition from $q_0$ to $q_1$ guesses the midpoint.
    • For odd-length strings (not in $L$), no guess works → rejects.
    • For $WW^r$, correct guess at exact middle → accepts.
    • DPDA cannot guess midpoint deterministically → $L$ not DCFL.

    ---

    Alternative: CFG

    $S \rightarrow aSa \mid bSb \mid \epsilon$ generates $L$.

    ---

    Final Answer

    NPDA with 3 states ($q_0, q_1, q_2$):

    • $q_0$: push $a,b$ onto stack while reading first half
    • $\epsilon$-transition: guess midpoint, switch to $q_1$
    • $q_1$: pop & match each input symbol with stack top
    • $\epsilon$ on $Z_0$: accept ($q_2$)
    • Accepts by final state $q_2$ and empty stack ($Z_0$ only).
15. Q3b. Eliminate \varepsilon, unit, and useless productions from the grammar: A → bA | Bba | aa B → aba | b | D C → CA | AC | B D → a | \varepsilon20237m

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

    Eliminate $\varepsilon$, unit, and useless productions from the grammar:

    A → bA | Bba | aa
    B → aba | b | D
    C → CA | AC | B
    D → a | $\varepsilon$

    View this question on its own page →

    CopySearch GoogleAsk AI
16. Q4a. Define Chomsky Normal Form. Convert the CFG: S → aSb | ab | Aa A → aab to CNF.20237m

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

    Define Chomsky Normal Form. Convert the CFG:

    S → aSb | ab | Aa
    A → aab

    to CNF.

    View this question on its own page →

    CopySearch GoogleAsk AI
17. Q4b. Obtain the regular expression for the given DFA. 20237m

    Module 1: Introduction & Regular Languages

    Obtain the regular expression for the given DFA.

    

    View this question on its own page →

    CopySearch GoogleAsk AI
18. Q5a. Prove that if L_1 and L_2 are regular, then L_1 \cup L_2 is regular.20237m

    Module 1: Introduction & Regular Languages

    Prove that if $L_1$ and $L_2$ are regular, then $L_1 \cup L_2$ is regular.

    View this question on its own page →

    CopySearch GoogleAsk AI
19. Q5b. Design a Turing machine that recognizes strings containing equal number of 0’s and 1’s.20237m

    Module 4: Turing Machines (TM)

    Design a Turing machine that recognizes strings containing equal number of $0$’s and $1$’s.

    View this question on its own page →

    CopySearch GoogleAsk AI
20. Q6a. Given the \varepsilon-NFA, compute \varepsilon-closures and convert to DFA. | State | \varepsilon-transition | a-transition | b-transition | |-------|--------------------------|--------------|--------------| | → | {r} | {q} | {p,r} | | q | ∅ | {p} | ∅ | | r | {p,q} | {r} | {p} |20237m

    Module 1: Introduction & Regular Languages

    Given the $\varepsilon$-NFA, compute $\varepsilon$-closures and convert to DFA.

    State	$\varepsilon$-transition	a-transition	b-transition
    →	{r}	{q}	{p,r}
    q	∅	{p}	∅
    r	{p,q}	{r}	{p}

    View this question on its own page →

    CopySearch GoogleAsk AI
21. Q6b. Construct NFA for the regular expression: (0+1)^*00(0+1)^*20237m

    Module 1: Introduction & Regular Languages

    Construct NFA for the regular expression:

    $$(0+1)^*00(0+1)^*$$

    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. Construct NPDA for the grammar: S \to \alpha ABB \mid \alpha AA \\ A \to \alpha BB \mid \alpha \\ B \to bBB \mid A20237m

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

    Construct NPDA for the grammar:

    $$S \to \alpha ABB \mid \alpha AA \\ A \to \alpha BB \mid \alpha \\ B \to bBB \mid A$$

    View this question on its own page →

    CopySearch GoogleAsk AI
24. Q7b. Prove the identity: (1+00^*1) + (1+00^*1)(0+10^*1)^*(0+10^*1) = 0^*1(0+10^*1)^*20237m

    Module 1: Introduction & Regular Languages

    Prove the identity:

    $$(1+00^*1) + (1+00^*1)(0+10^*1)^*(0+10^*1) = 0^*1(0+10^*1)^*$$

    View this question on its own page →

    CopySearch GoogleAsk AI
25. Q8a. Construct a Moore machine equivalent to the given Mealy machine.20237m

    Module 1: Introduction & Regular Languages

    Construct a Moore machine equivalent to the given Mealy machine.

    View this question on its own page →

    CopySearch GoogleAsk AI
26. Q8b. Given the grammar: S \to aB \mid ba \\ B \to b \mid bs \mid aBB For the string aaabbabbba find: 1. Leftmost derivation 2. Rightmost derivation 3. Parse tree20237m

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

    Given the grammar:

    $$S \to aB \mid ba \\ B \to b \mid bs \mid aBB$$

    For the string $aaabbabbba$ find:

    1. Leftmost derivation
    2. Rightmost derivation
    3. Parse tree

    View this question on its own page →

    CopySearch GoogleAsk AI
27. Q9a. Write short notes on: Post Correspondence Problem.20237m

    Module 5: Undecidability

    Write short notes on: Post Correspondence Problem.

    View this question on its own page →

    CopySearch GoogleAsk AI
28. Q9b. Write short notes on: Multi-tape Turing Machine.20237m

    Module 4: Turing Machines (TM)

    Write short notes on: Multi-tape Turing Machine.

    View this question on its own page →

    CopySearch GoogleAsk AI
29. Q9c. Write short notes on: NP-hard and NP-complete problems.20237m

    Module 5: Undecidability

    Write short notes on: NP-hard and NP-complete problems.

    View this question on its own page →

    CopySearch GoogleAsk AI
30. Q9d. Write short notes on: Pumping lemma for CFL.20237m

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

    Write short notes on: Pumping lemma for CFL.

    View this question on its own page →

    CopySearch GoogleAsk AI