Context Free Grammars and Languages

\(A \to a \mid aA\) generates \(a^{n}\) and \(B \to b \mid bB\) generates \(b^{n}\), for \(n \ge 1\).

So \(S \to aaB\) gives the strings \(a^{2}b^{n}\), and \(S \to Abb\) gives the strings \(a^{n}b^{2}\). Together, \(L(G) = \{a^{2}b^{n} \mid n \ge 1\} \cup \{a^{n}b^{2} \mid n \ge 1\}\).

The other options do not match: for example, \(aabbb \in L(G)\), but it belongs to none of (B), (C) and (D).

Answer: A

• \(L_2\) is context-free: \(a^m b^n c^{m+n} = a^m\,(b^n c^n)\,c^m\) is a nested pattern, generated by \(S \to aSc \mid aAc\), \(A \to bAc \mid bc\). A PDA pushes one symbol for every \(a\) and \(b\) and pops one for every \(c\).
• \(L_1\) is not context-free: it needs \(\#a = \#b\) and also \(\#c \gt \#a\) (because \(n \ge 1\)), so the same count \(m\) must be compared twice, but the single stack is used up matching the a's against the b's.
• Pumping lemma check: take \(a^p b^p c^{p+1}\). The pumped part (length \(\le p\)) cannot touch both a's and c's. If it contains a's or b's, pumping up gives \(\#a \ne \#b\) or \(\#a = \#b \ge p + 1 = \#c\); if it contains only c's, pumping down gives \(\#c \le p = \#a\). Either way the string leaves \(L_1\).

Answer: C

Test each class against each property:

• Context-free languages are closed under union but not under intersection or complementation. For example, with \(m, n \ge 0\), \(\{a^{n}b^{n}c^{m}\}\) and \(\{a^{m}b^{n}c^{n}\}\) are context-free, but their intersection \(\{a^{n}b^{n}c^{n}\}\) is not. So (i) fits (a) and (b), not (c).
• Recursive languages are closed under union, intersection and complementation (swap a decider's accept and reject answers). So (ii) fits (a) and (c), not (b).
• Regular languages are closed under all three as well, so (iii) fits (a) and (c), not (b).

Option A fails on (ii) – (b) and option D on (iii) – (b), while every pair in B and C is true.

Answer: B, C

In Chomsky Normal Form every rule has the form \(A \rightarrow BC\) or \(A \rightarrow a\), and \(|w| = 90\).

• Each \(A \rightarrow BC\) step adds one symbol to the sentential form. Growing from the single symbol \(S\) to 90 symbols takes exactly 89 such steps.
• Each \(A \rightarrow a\) step turns one variable into one terminal, and every one of the 90 terminals is produced this way: 90 steps.

The derivation therefore has \(89 + 90 = 179\) steps. In general a CNF derivation of a string of length \(n \ge 1\) takes \(2n - 1\) steps; the 10 variables do not affect the count.

Answer: 179

Follow the counts through a derivation, which starts with one \(S\). The rule \(S \rightarrow aSbS\) adds one \(a\), one \(b\) and one extra \(S\); \(S \rightarrow aS\) adds one \(a\); \(S \rightarrow c\) turns one \(S\) into \(c\). Every \(S\) must finally become a \(c\), so:

• \(n_c(w) = 1 + n_b(w)\), so (C) is true.
• Every \(b\) arrives with an \(a\), so \(n_a(w) \ge n_b(w) = n_c(w) - 1 \gt n_c(w) - 2\), and (B) is true.

The string \(w = c\) has \(n_a = n_b = 0\) and \(n_c = 1\). It breaks (A), since \(0 \gt 0\) is false, and (D), since \(1 \ne 0\).

Answer: B, C