Test Your Knowledge on CFG
Multiple Choice Questions (MCQ)
Q.1) If G is a grammar with productions
S → SaS | aSb | bSa | SS |∈
Where S is the start variable, then which one of the following strings is not generated by G?
(A) abab
(B) aaab
(C) abbaa
(D) babba
Solution:
Thus, the string which is not generated by the given grammar G is babba
Q.2) Identify the language generated by the following grammar, where S is the start variable.
S → XY
X → aX|a
Y → aYb|∈
(A) abcba & bacab
(B) abcba & abcab
(C) acca & bcccb
(D) acccb & bccca
Solution:
The language defined by the given grammar is odd length palindrome formed using alphabets {a, b} with c as the middle alphabet.
Thus, option (A) is the correct answer.
Problems to Solve
Q.4) The following grammar generates the language of regular expression 01(0+1):
S --> A1B
A --> 0A | ε
B --> 0B | 1B | ε
Give leftmost and rightmost derivations of the following strings:
a) 00101
b) 1001
c) 00011
Solution:
Q.5) The following productions define the grammar of the language consisting of all strings of even length:
S --> AS | ε
A --> aa | ab | ba | bb
Give leftmost and rightmost derivations of the following strings:
a) aabbba
b) baabab
c) aaabbb
Q.6) Consider the CFG G defined by productions:
S --> aSbS | bSaS | ε
Prove that L(G) is the set of all strings with an equal number of a's and b's
Q.7) Find a derivation tree of
a * b + a * b
given that a * b + a * b is in L(G), where G is defined as follows:
S --> S + S | S* S, S --> a | b
Q.8) Consider the following productions:
S --> aB | bA
A --> aS | bAA | a
B --> bS | aBB | b
For the strings aaabbabbba, find:
a) the leftmost derivation
b) the rightmost derivation and
c) the parse tree.
Q.9)
Q.10)
Q.11)
Q.13)
