Context Free Grammars Questions and Answers

Answer: D

The grammar generates \(\{a,b\}^{*}\).

\(S \rightarrow aS \mid bS \mid \varepsilon\) lets each step add either an a or a b at the front and continue, or stop. Any string of a's and b's in any order, including the empty string, can be built letter by letter, so the language is all strings over \(\{a, b\}\).

\(\{a^{n}b^{m}\}\) forces all a's before the b's, but the grammar also gives ba. Nothing in the grammar counts letters, so the 'equal number' and \(a^{n}b^{n}\) options are far too narrow, and the grammar also produces strings like aab.

Answer: D

\(G_{1}\) and \(G_{2}\) generate \(\{a^{m}b^{n} \mid m \ge 0 \text{ and } n \gt 0\}\) and \(\{a^{m}b^{n} \mid m \gt 0 \text{ or } n \gt 0\}\).

\(G_{1}\): \(S \rightarrow aS \mid B\) produces any number of a's, possibly none, then switches to \(B\). \(B \rightarrow b \mid bB\) produces one or more b's. So \(m \ge 0\) and \(n \gt 0\).

\(G_{2}\): \(S\) must start with a (then \(A\)) or b (then \(B\)). From \(A\), any number of further a's, then optionally \(B\), which gives any number of b's including none. From the b start, only b's follow. So every string is \(a^{m}b^{n}\) with at least one symbol: \(m \gt 0\) or \(n \gt 0\). The empty string is excluded because \(S\) has no \(\varepsilon\) rule.

The other options get one of these conditions wrong, for example 'm \(\gt\) 0 and n \(\gt\) 0' for \(G_{2}\) would exclude 'a' and 'b', which \(G_{2}\) generates.

Answer: A

The language is \(\{a^{2}b^{n} \mid n \ge 1\} \cup \{a^{n}b^{2} \mid n \ge 1\}\).

B generates \(b^{n}\) for \(n \ge 1\) and A generates \(a^{n}\) for \(n \ge 1\). The first rule \(S \rightarrow aaB\) therefore gives exactly two a's followed by one or more b's, \(a^{2}b^{n}\). The second rule \(S \rightarrow Abb\) gives one or more a's followed by exactly two b's, \(a^{n}b^{2}\). The language is the union of the two.

The other options demand a link between the numbers of a's and b's (such as \(a^{n}b^{n}\) or \(a^{n}b^{2n}\)), but in this grammar the a's and b's are generated by separate rules with nothing tying the counts together. For example aabbb is in L(G) but has unequal counts.

Answer: C

P is false and Q is true.

\(S_{1} \rightarrow aS_{1}b \mid \varepsilon\) generates \(L_{1} = \{a^{n}b^{n} : n \ge 0\}\). Recognising it needs to count the a’s to match the b’s, and the pumping lemma shows it is not regular, so P is false.

\(S_{2} \rightarrow abS_{2} \mid \varepsilon\) generates \(L_{2} = (ab)^{*}\), any number of repetitions of the string ab. It is a right-linear grammar, and the regular expression \((ab)^{*}\) describes it, so Q is true.

Options calling \(L_{1}\) regular, or \(L_{2}\) non-regular, are therefore wrong.

Answer: B

The language is \(a^{*}(a+b)b^{*}\).

Start with X. The rules X \(\to\) aX and X \(\to\) Xb add any number of a's on the left and b's on the right, and the derivation ends with a single a or b in the middle. So X generates \(a^{*}(a+b)b^{*}\): some a's, then one a or b, then some b's.

S \(\to\) aSb wraps that in n further a's and n further b's, giving \(a^{n}a^{*}(a+b)b^{*}b^{n}\), which is still \(a^{*}(a+b)b^{*}\). The matching counts add nothing, because X can already produce any numbers of a's and b's on its own.

\((a+b)^{*}\) includes the empty string and strings like ba, which G cannot produce, since every b comes after every a. \(a^{*}b^{*}(a+b)\) contains bba, which G cannot generate. And since the language is given by a regular expression, it is regular.

Answer: C

The resulting grammar has 10 productions.

The unit productions are S \(\to\) B, B \(\to\) A and A \(\to\) B, so B and A can each derive the other, and S can derive both. Removing them, each variable takes the non-unit productions of every variable it can reach through unit productions. The non-unit productions are S \(\to\) Aa, B \(\to\) bb and A \(\to\) a | bc.

• S \(\to\) Aa | bb | a | bc: 4 productions
• B \(\to\) bb | a | bc: 3 productions
• A \(\to\) a | bc | bb: 3 productions

That makes 4 + 3 + 3 = 10. Counts such as 11, 12 or 18 come from keeping a unit production or duplicating a substituted one.

Answer: B

The Chomsky Normal Form grammar has 8 productions.

In CNF every production is either \(A \rightarrow BC\) or \(A \rightarrow a\). Introduce a variable for each terminal and break the long right-hand sides into pairs:

\[ \begin{aligned} S &\rightarrow A X_1, \quad X_1 \rightarrow B T_a \\ A &\rightarrow T_a X_2, \quad X_2 \rightarrow T_a T_b \\ B &\rightarrow A T_c \\ T_a &\rightarrow a, \ T_b \rightarrow b, \ T_c \rightarrow c \end{aligned} \]

That is 2 for S, 2 for A, 1 for B and 3 terminal productions: 8 in all. The grammar has no null or unit productions to remove first. Six productions are too few once the two length-3 right-hand sides are split into pairs, and 9 or 10 would include productions CNF does not need.

Answer: B

The correct grammar is option (B).

Start with \(S \to abc\) for \(n = 1\). For larger \(n\), \(S \to aAbc\) begins a derivation, and the rules \(Ab \to bA\) and \(Ac \to Bbcc\) move \(A\) to the right past the b and turn it into one more b and c. Then \(bB \to Bb\) carries \(B\) back left to the a's, and \(aB \to aa\) ends with one more a. For \(n = 2\):

\[ \begin{aligned} S &\Rightarrow aAbc \Rightarrow abAc \\ &\Rightarrow abBbcc \Rightarrow aBbbcc \Rightarrow aabbcc \end{aligned} \]

The rule \(aB \to aaA\) restarts the cycle for larger \(n\). Option A has no rule giving \(abc\), and its \(S \to aSbc\) puts the b and c in the wrong places (it derives \(aaabbccbc\)). Option C has \(Ab \to Ab\), which changes nothing, so \(A\) never reaches the c. Option D drops the contexts: \(S \Rightarrow aAbc \Rightarrow aBbccbc \Rightarrow aabccbc\), which is not of the form \(a^{n}b^{n}c^{n}\).

Answer: B

Such rules are called Syntactic rules.

Syntax concerns the form and arrangement of words and symbols, the grammatical structure of a sentence or program, regardless of what it means. A sentence can be syntactically correct and still meaningless.

Semantics is the study of meaning, which is exactly what these rules leave out, so 'Semantics' and 'Both (a) and (b)' are wrong.

In a compiler, the parser checks syntax, while meaning, such as type correctness, is checked in the separate semantic analysis phase.

Answer: C

Context-free languages are generated by Type 2 grammars.

In a context-free grammar every production has a single non-terminal on the left, A → α, so A can be rewritten whatever surrounds it. These are Type 2 in the Chomsky hierarchy and are accepted by pushdown automata.

Type 0 grammars are unrestricted and generate recursively enumerable languages. Type 1 grammars are context-sensitive. Type 3 grammars are regular.