Theory Of Computation MCQ - Context free languages


The CFG 
s---> as | bs |  a |  b

is equivalent to regular expression

A. (a + b)
B. (a + b) (a + b)*
C. (a + b) (a + b)
D. None of these

Option: B

Explanation :


Consider the grammar :

S —> ABCc | Abc
BA —> AB
Bb —> bb
Ab —> ab
Aa —> aa 

Which of the following sentences can be derived by this grammar 

A. abc
B. aab
C. abcc
D. abbb

Option: A

Explanation :


Pumping lemma is generally used for proving that

A. given grammar is regular
B. given grammar is not regular
C. whether two given regular expressions are equivalent or not
D. None of these

Option: B

Explanation :


The language of all words with at least 2 a's can be described by the regular expression

A. (ab)*a and a (ba)*
B. (a + b)* ab* a (a + b)*
C. b* ab* a (a + b)*
D. all of these

Option: D

Explanation :


Any string of terminals that can be generated by the following CFG is
S-> XY
X--> aX | bX | a 
Y-> Ya  | Yb | a

A. has atleast one 'b'
B. should end in a 'a'
C. has no consecutive a's or b's
D. has atleast two a's

Option: D

Explanation :

Suggest an improvement