Properties of Context Free Languages Questions and Answers

Answer: C

The correct statement is L₁ is not regular, but L₂ is regular.

L₂ is regular. Here \(\alpha\) is a string of a's only, so a word \(\alpha\beta\alpha\) starts and ends with a. Conversely, any word over {a, b} that starts with a, ends with a and has length at least 3 can be written with \(\alpha = a\) and \(\beta\) the nonempty middle. So L₂ is the language of the expression \(a(a + b)^{+}a\), which is regular.

L₁ is not regular. Now \(\alpha\) can be any string over {a, b}, so the first and last symbols of a word need not be equal. Take the words \(a b^{i} a a b^{j}\) with \(i, j \ge 1\). Such a word ends in b, so \(\alpha\) must end in b, and being a prefix \(\alpha\) must start with a. The only suffix starting at an a and ending in b that is short enough is \(a b^{j}\) (the longer suffix \(a a b^{j}\) would need the word to start with aa, but it starts with ab). That \(\alpha\) is also a prefix exactly when \(i \ge j\), and then the middle part is nonempty. So

\[ \begin{aligned} L_{1} \cap a b^{+} a a b^{+} &= \\ & \{ a b^{i} a a b^{j} \mid i \ge j \ge 1 \} \end{aligned} \]

This language is not regular, since a finite automaton cannot compare the number of b's before and after the aa. Regular languages are closed under intersection with the regular language \(a b^{+} a a b^{+}\), so if L₁ were regular this intersection would be regular. Hence L₁ is not regular.

The easy mistake is to read L₁ as the words whose first and last symbols are equal, which is regular. That ignores that \(\alpha\) may have several symbols and that only the word as a whole has to start and end with the same string \(\alpha\). So option C is correct, and A, B and D are not.

Answer: C

The correct statement is \(L_{1}\) is not a context-free language but \(L_{2}\) is a context-free language.

\(L_{2} = \{a^{m}b^{n}c^{m+n}\}\) is context-free: a pushdown automaton pushes a symbol for each a and each b and pops one for each c. A grammar is \(S \rightarrow aSc \mid aBc\), \(B \rightarrow bBc \mid bc\), which wraps each a and each b with its own c.

\(L_{1} = \{a^{m}b^{m}c^{m+n}\}\) needs the a's and b's to be equal and the c's to exceed them. A single stack cannot do both: matching a's against b's uses up the count before the c's arrive. The pumping lemma confirms it with \(a^{p}b^{p}c^{p+1}\): any pumped segment of length at most p either upsets the a = b balance or, by pumping, makes the a's and b's reach or pass the number of c's, or the c's fall to the number of a's.

So only option C is right; options A and B wrongly call \(L_{1}\) context-free, and D wrongly excludes \(L_{2}\).

Answer: B

\(L_{1}\) is context-free while \(L_{2}\) is not context-free.

\(L_{1} = \{a^{n}b^{m}c^{n+m}\}\) is context-free: rewrite it as \(a^{n}b^{m}c^{m}c^{n}\), which nests a \(b^{m}c^{m}\) block inside an \(a^{n} \ldots c^{n}\) block. The grammar \(S \rightarrow aSc \mid aTc\), \(T \rightarrow bTc \mid bc\) generates it, and a pushdown automaton pushes for each a and b and pops for each c.

\(L_{2} = \{a^{n}b^{n}c^{2n}\}\) needs the counts of a, b and c compared together, like \(a^{n}b^{n}c^{n}\). A single stack cannot check both equalities, and the pumping lemma for context-free languages shows it is not context-free.

So the options calling \(L_{2}\) context-free, or \(L_{1}\) not context-free, are wrong.

Answer: B

The context-free languages are I and II only.

I: \(m + p = n + q\) says the a's and c's together balance the b's and d's. A pushdown automaton can push a symbol for each a, cancel against each b (pushing a different marker once the a's run out), and do the same for the c's and d's, accepting when the stack is empty, so I is context-free.

II is the concatenation of \(\{a^{m}b^{m}\}\) and \(\{c^{p}d^{p}\}\), both context-free, so it is context-free.

III is not: intersecting it with the regular language \(a^{*}b^{*}c^{*}\) (forcing \(q = 0\)) leaves \(\{a^{n}b^{n}c^{n} : n \ge 1\}\), which is not context-free, and context-free languages are closed under intersection with regular languages. IV is not either: with \(q = 0\) it becomes \(\{a^{m}b^{n}c^{mn}\}\), which needs a product of two counts. So the options containing III or IV are wrong.

Answer: C

The correct statements are (i) and (ii) only.

Statement (i), read with the printed 'ρDA' as PDA (pushdown automaton), is the definition of a deterministic context-free language: one accepted by some deterministic PDA. Statement (ii) is the definition of an inherently ambiguous language: every grammar generating it is ambiguous.

Statement (iii) is wrong: productions of the form A → BC and A → a define Chomsky Normal Form. In Greibach Normal Form every production has the form A → aα, a terminal followed by a string of non-terminals.