Context Free Grammars Questions and Answers

Answer: B

The Chomsky hierarchy is a classification of formal grammars and languages.

Noam Chomsky (1956) arranged grammars in four nested types by how restricted their production rules are: Type 0 unrestricted (recursively enumerable), Type 1 context-sensitive, Type 2 context-free, and Type 3 regular. Each type matches a class of automaton, from Turing machines down to finite automata.

It does not classify programming languages, although they are usually specified with context-free grammars. Nor does it classify algorithms or data structures.

Answer: D

The most powerful is the Unrestricted grammar.

In the Chomsky hierarchy each type contains the next: unrestricted (type 0) grammars generate the recursively enumerable languages accepted by Turing machines; context-sensitive (type 1) grammars generate the languages of linear bounded automata; context-free (type 2) grammars those of pushdown automata; and regular (type 3) grammars those of finite automata.

So regular grammars are the weakest, and every context-free and context-sensitive language can also be generated by an unrestricted grammar.

Answer: A

The key takes the 'C' language to be a context-free language. The syntax of C is defined by a context-free grammar in its reference manual, and parsers such as those produced by yacc are built from that grammar, so for the purpose of this question C is treated as context free.

Strictly, rules like declaring a name before its use are context sensitive, which is why 'Context sensitive language' is the other option someone might choose. It is not the answer in the key. A regular language is much too weak to describe C, which has nested blocks and expressions, so that option is wrong.

Answer: B

Reading the first grammar as \(S \to 0S0 \mid 1S1 \mid 0 \mid 1 \mid \epsilon\), it generates the palindromes over {0, 1}, and each palindrome has just one parse tree, since the first and last symbols fix the rule to use, so G1 is unambiguous. The second grammar, \(S \to aS \mid aSb \mid X\), \(X \to Xa \mid a\), is ambiguous: the string aa has one derivation \(S \Rightarrow aS \Rightarrow aX \Rightarrow aa\) and another \(S \Rightarrow X \Rightarrow Xa \Rightarrow aa\). So G1 is unambiguous and G2 is ambiguous, the second option.

Answer: B

The language \(L = \{ww^R\}\) is the set of even length palindromes over {a, b}, so each string is built by putting the same letter at both ends and repeating, until the empty string. The grammar \(S \to aSa \mid bSb \mid \epsilon\) does exactly this. The grammar with asb and bsa generates strings in which the ends differ, such as ab, which is not of the form ww^R, and the last option, which has no \(\epsilon\) rule, cannot generate the empty string, which is in L (with w empty). The keyed answer is the second option.

Answer: C

A grammar is in Greibach normal form when every production has the form of a terminal followed by zero or more variables. In (i) every production starts with a terminal, so it is in the form. In (ii) the production S to AB begins with a variable, so (ii) is not. In (iii) the production S to A has a single variable on the right and no terminal, so (iii) is not either. So the grammars that are not in Greibach normal form are (ii) and (iii), option (C).

Answer: D

The grammar has B going to aBb or to the empty string, and A going to BB, so B and A can both be empty. To remove the empty productions, add a version of each rule with the nullable variable left out: S goes to aA or to a, A goes to BB or to B, and B goes to aBb or to ab. This gives S to a | aA, A to BB | B, B to aBb | ab, option (D). Option (A) leaves the empty string out without compensating, and options (B) and (C) each miss the rule A to B or the rule B to ab.

Answer: C

The grammar generates strings with equal numbers of a's and b's. A generates the strings that have one more a than b's, B generates those with one more b than a's, and S starts with a followed by a string with one more b, or b followed by a string with one more a, so the totals are always equal. A check: S gives aB which gives ab, and bA gives ba, each with one a and one b. So the strings have an equal number of a's and b's, option (C). The options on odd, even and unequal counts are therefore wrong.

Answer: B

A regular grammar generates the languages accepted by a deterministic finite automaton (c). A context free grammar generates the languages accepted by a pushdown automaton (a). An unrestricted grammar generates the languages accepted by a Turing machine (d), and a context sensitive grammar those accepted by a linear bounded automaton (b). So the code is (c), (a), (d), (b), option (B). Options (A), (C) and (D) swap the Turing machine with the linear bounded automaton or the pushdown automaton, which do not match.

Answer: D

The key gives the last grammar. The language has n a's followed by m b's with n at most m + 3. The non-terminal A generates a^k b^j with j at least k, using aAb to match pairs and B to add extra b's. Prefixing aaa, aa or a before A allows one, two or three surplus a's, and the last option lists all three prefixes together with the empty string.

The other options offer fewer prefixes, so they leave out some strings with two or one surplus a's. Strictly no option generates strings with no surplus a such as 'ab' or 'b', but the last option is the nearest and is the one the body intended.