Let G be a context-free grammar where G = ( { S, A, B, C}, { a,b, d}, P, S ) with the productions in P given below.
S ? ABAC
A ? aA ? ?
B ? bB ? ?
C ? d
(? denotes null string). Transform the grammar G to an equivalent context-free grammar G' that has no ? productions and no unit productions. (A unit production is of the form x ? y, and x and y are non terminals.)
A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals. S?aS?A A?aAb?bAa?? For the correct answer in Q75, how many steps are required to derive the string and how many parse trees are there?
Given the following statements: (i) Recursive enumerable sets are closed under complementation. (ii) Recursive sets are closed under complements. Which is/are the correct statements?
Correct Answer: B
Recursive languages are closed under the following operations.
The Kleene star L * of L
The concatenation L * o P of L and P
The union L U P
The intersection L ? P.
