Classical

Theory Of Computation MCQ - Context free languages

16:  

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 :


17:  

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 :


18:  

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 :


19:  

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 :


20:  

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