Classical

Theory Of Computation MCQ - Context free languages

36:  

 Let L be a language recognizable by a finite automaton. The language

                       REVERSE (L) = {w such that w is the reverse of v where v ∈ L } is a

A.

regular language

B.

context-free language

C.

context-sensitive language

D.

recursively enumerable language

 
 

Option: A

Explanation :


37:  

 The grammars G = ( { s }, { 0, 1 }, p , s)
where p = (s —> 0S1, S —> OS, S —> S1, S —>0} is a

A.

recursively enumerable language

B.

regular language

C.

context-sensitive language

D.

context-free language

 
 

Option: B

Explanation :


38:  

The logic of pumping lemma is a good example of

A.

pigeon-hole principle

B.

divide-and-conquer technique

C.

recursion

D.

iteration

 
 

Option: A

Explanation :

The  pigeon hole principle is nothing more than the obvious remark: if you have fewer pigeon holes than pigeons and you put every pigeon in a pigeon hole, then there must result at least one pigeon hole with more than one pigeon. It is surprising how useful this can be as a proof strategy.
In the theory of formal languages in computability theory, a pumping lemma or pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of times, with the resulting string remaining in that language. The proofs of these lemmas typically require counting arguments such as the pigeonhole principle. So the answer is 'A'


39:  

 The intersection of CFL and regular language

A.

is always regular

B.

is always context free

C.

 both (a) and (b)

D.

need not be regular

 
 

Option: B

Explanation :


40:  

 For two regular languages

L1 = (a + b)* a and L2 = b (a + b ) *

the intersection of L1 and L2 is given by 

A.

(a + b ) * ab

B.

ab (a + b ) *

C.

a ( a + b ) * b

D.

b (a + b ) * a

 
 

Option: D

Explanation :




Suggest an improvement