FORMAL LANGUAGE & AUTOMATA THEORY

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.

Answer

Correct Option: (iii) Intersection

Explanation

Closure properties of Context-Free Languages (CFLs):

Operation	Closed?
Union $L_1 \cup L_2$	Yes – $S \rightarrow S_1 \mid S_2$
Concatenation $L_1L_2$	Yes – $S \rightarrow S_1S_2$
Kleene star $L^*$	Yes – $S \rightarrow SS_1 \mid \epsilon$
Intersection $L_1 \cap L_2$	No
Complement $\overline{L}$	No

Counterexample for intersection:
$L_1 = \{a^n b^n c^m \mid n,m\ge0\}$ (CFL), $L_2 = \{a^m b^n c^n \mid n,m\ge0\}$ (CFL)
$L_1 \cap L_2 = \{a^n b^n c^n\}$ which is not CFL (pumping lemma).

Since De Morgan: $L_1 \cap L_2 = \overline{\,\overline{L_1}\cup\overline{L_2}\,}$, non-closure under intersection implies non-closure under complement.

Final Answer

CFLs are NOT closed under Intersection → Option (iii).

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).

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.

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).

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).

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).

Answer

Correct Option: (i) $\{a^n b^n\}$

Explanation

Deterministic CFL (DCFL): Accepted by DPDA (deterministic pushdown).

• (i) $\{a^n b^n\}$: DPDA can push $a$'s, then pop for $b$'s, deterministic (no choice). DCFL.
• (ii) Arithmetic expressions (e.g., $E \rightarrow E+E \mid E*E$) → inherently ambiguous, CFL but not deterministic (needs guessing).
• (iii) Palindromes $\{ww^R\}$ → not deterministic (needs to guess middle). $\{w\#w^R\}$ is DCFL, but plain palindromes is NPD A.
• (iv) $\{ww^R\}$ similar to (iii) — not DCFL.

Hence only $\{a^n b^n\}$ is deterministic.

Final Answer

$\{a^n b^n\}$ is DCFL → Option (i).

Answer

Correct Option: (i) Finite automaton with a stack

Explanation

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

• Essentially a finite automaton (finite control) augmented with a stack (LIFO memory).
• Stack provides unbounded memory but restricted access (push/pop at top only).
• Enables recognition of CFLs: e.g., $\{a^n b^n\}$ by pushing $a$'s, popping for $b$'s.

Options:

• (ii) TM with stack → equivalent to TM (stack is not needed)
• (iii) FA with queue → queue automaton = TM-powerful
• PDA = FA + stack.

Final Answer

PDA = FA + stack → Option (i).

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.

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).

Answer

Theorem: $L$ is accepted by a PDA $\iff$ $L$ is generated by a CFG (i.e., CFL = NPDA languages).

We prove PDA $\rightarrow$ CFG using the Triplet Construction (Sipser / standard textbook method).

---

Given

PDA $P = (Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ accepting $L(P)$ by final state (empty stack can be converted).

Assume $\delta$ has no $\epsilon$-transitions on input (can be eliminated). If $\epsilon$-moves exist, handle via closure.

---

Construction of CFG $G = (V, \Sigma, R, S)$

Variables $V$:

• Start symbol $S$
• Triplet variables $[p A q]$ for every $p,q \in Q$ and $A \in \Gamma$
  • Meaning: "Starting in state $p$ with stack top $A$, $P$ can reach state $q$ with $A$ popped off (and any symbols pushed above it matched)."

Productions $R$:

1. Start: $S \rightarrow [q_0 Z_0 p]$ for each $p \in F$

   • Begin at $q_0$ with initial stack $Z_0$, end in any final state $p$.

2. From PDA transitions:
   For every transition $\delta(p, a, A)
   i (q, \alpha)$where$a \in \Sigma \cup {\epsilon}$:

   • Case $\alpha = \epsilon$ (pop $A$, no push):
     $$[p A q] \rightarrow a$$
     (if $a=\epsilon$, RHS is $\epsilon$)

   • Case $\alpha = B_1 B_2 \dots B_k$ ($k \ge 1$):
     For all $r_1, r_2, \dots, r_{k+1} \in Q$:
     $$[p A r_{k+1}] \rightarrow a\; [q B_1 r_1]\; [r_1 B_2 r_2] \dots [r_k B_k r_{k+1}]$$

     • Push $B_1\dots B_k$; must pop them in order via intermediate states.
     • $a$ consumed on transition; each $[r_i B_{i+1} r_{i+1}]$ matches push/pop of $B_{i+1}$.

3. Empty stack (optional, for empty-stack acceptance):
   Add $[p \epsilon p] \rightarrow \epsilon$ for all $p \in Q$ (not needed for final-state).

---

Intuition of Triplet $[p A q]$

• Represents a matching push-pop pair on symbol $A$.
• $p$: state where $A$ is pushed
• $q$: state where $A$ is popped
• The derivation inside $[p A q]$ generates the string read between push and pop of $A$.

---

Proof of Correctness (Sketch)

Soundness (CFG $\subseteq$ PDA):
Every derivation in $G$ corresponds to a valid PDA computation:

• $S \Rightarrow^* [q_0 Z_0 p]$ maps to initial config.
• Production $[p A r] \rightarrow a [q B r_1] \dots$ mimics transition $(p,a,A) \to (q,B\dots)$.
• Base case $[p A q] \rightarrow a$ mimics $(p,a,A) \to (q,\epsilon)$.
• Induction on derivation length shows derived string is accepted by $P$.

Completeness (PDA $\subseteq$ CFG):
For any accepting run of $P$ on $w$, build a parse tree in $G$:

• Root $S \to [q_0 Z_0 p]$.
• Each push of $A$ at state $p$ and corresponding pop at $q$ gives variable $[p A q]$.
• The substring read between push and pop is generated by that variable.
• By induction on height of push-pop pairs, $w$ is generated.

---

Example

PDA for $\{a^n b^n\}$:

• $\delta(q_0, a, Z_0) = (q_0, XZ_0)$
• $\delta(q_0, a, X) = (q_0, XX)$
• $\delta(q_0, b, X) = (q_1, \epsilon)$
• $F = \{q_1\}$

CFG variables: $S, [q_0 Z_0 q_1], [q_0 X q_0], [q_0 X q_1], \dots$
Productions:
$S \rightarrow [q_0 Z_0 q_1]$
$[q_0 X q_1] \rightarrow a [q_0 X q_1] b \mid ab$ (after resolving all intermediate states)
$[q_0 Z_0 q_1] \rightarrow a [q_0 X q_1] b$

Yields $a^n b^n$.

---

Formal Statement

Theorem: $L$ is accepted by a (nondeterministic) PDA iff $L$ is generated by a CFG.
Corollary: CFL = languages accepted by NPDA. DPDA $\subset$ CFL (strict).

---

Final Answer

Proof via Triplet Construction: Create CFG with variables $[p A q]$ representing push-pop of $A$ from state $p$ to $q$. Productions mirror PDA transitions. $S \to [q_0 Z_0 p]$ for final $p$. Induction on derivations/computations proves $L(G) = L(P)$. Hence every PDA language is a CFL.