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 :

Click on Discuss to view users comments.

Write your comments here:



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 :

Click on Discuss to view users comments.

DIVYA said: (4:33pm on Monday 3rd October 2016)
S->Abc,s->abc so the answer is (A),S->ABCc,it is not non terminal terms in grammar

Write your comments here:



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 :

Click on Discuss to view users comments.

Write your comments here:



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 :

Click on Discuss to view users comments.

Write your comments here:



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 :

Click on Discuss to view users comments.

samra said: (11:33am on Saturday 9th June 2018)
what will be regular expression for this cfg?

Write your comments here: