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
Q.2) Identify the language generated by the following grammar, where S is the start variable.
S → XY
X → aX|a
Y → aYb|∈
Q.3) If a grammar G has three productions:
S --> aSa | bSb | c
then which of the following strings are part of the language recognized by CFG?
(A) abcba and bacab
(B) abcba and abcab
(C) acca and bcccb
(D) acccb and bccca
Problems to Solve:
The following grammar generates the language of regular expression 0 1 ( 0 + 1 ) :
S --> A1B
A --> 0 A |
B ! 0 B j 1 B j
Give leftmost and rightmost derivations of the following strings:
* a) 00101.
b) 1001.
c) 00011.
