Q1. Consider turing machines as enumerators.

We define a language L=[<M>| M is the encoding a turing machine that enumerates the strings it accepts in lexicographic order}.

Choose the correct statement.

a. L is a csl

b. L is recursive

c. L is r.e. and not recursive

d. L is not r.e.



Q2.Ram and Shyam decide to classify a hierarchy of turing machines as follows:

L0={<M>|M is the encoding of turing machines that accept the recursive sets}

L1={<M>|M is the encoding of turing machines that accept the csls}

L2={<M>|M is the encoding of turing machines that accept the cfls}

L22={<M>|M is the encoding of turing machines that accept the dcfls}

L3={<M>|M is the encoding of turing machines that accept the regular sets}

L4={<M>|M is the encoding of turing machines that accept the finite sets}

Choose the correct statement

a. all the above languages are recursive

b. all the above languages are r.e.

c. all the above languages are not r.e.

d. all the above languages are r.e and not recursive



Q3. The grammar

S---->aSbS|bSaS|e is

a. ambiguous

b. generates an inherently ambiguous language

c. is not ambiguous

d. generates an unequal number of a's and b's



Q4. The grammar

S------>aSbS|bSaS|e i

a. generates an equal number of a's and b's

b. generates an unequal number of a's and b's

c. generates more a's than b's

d.generates more b's than a's



Q5. The grammar

S--->aB|bA

A----->a|aS|bAA

B----->b|bS|aBB

a. is ambiguous

b. generates an inherently ambiguous language

c.is unambiguous

d. generates an unequal number of a's and b's



Q6. The grammar

S--->aB|bA

A----->a|aS|bAA

B----->b|bS|aBB

a. generates an equal number of a's and b's

b. generates an inherently ambiguous language

c.generates more a's than b's

d. generates an unequal number of a's and b's



Q7. The grammar

S--->aSBC|aBC

aB--->ab

bB---->bb

bC--->bc

cC---->cc

a. generates a regular set

b.generates a cfl

c. generates a dcfl

d. generates a csl



Q8. The grammar

S--->aSBC|aBC

aB--->ab

bB---->bb

bC--->bc

cC---->cc

a. generates the set of all strings with an equal number of a's, b's and c's

b.generates {a^nb^n C^n|n>=1}l

c. generates more a's than b'sl

d. generates more b's than c's



Q9. The grammar

S--->aSBC|aBC

aB--->ab

bB---->bb

bC--->bc

cC---->cc

a. is type-0 and not type-1

b.type-1 and not type-2

c. type-2 and not type-1l

d. type-3 and not type-2



Q10. The grammar

S--->aSBC|aBC

aB--->ab

bB---->bb

bC--->bc

cC---->cc

a. is in CNF form

b.is in GNF form

c. generates a dcfl that is not regular

d. generates a csl that is not regular



Q11. The grammar

S--->aSBC|aBC

aB--->ab

bB---->bb

bC--->bc

cC---->cc

generates a language that can be accepted by a

a. linear bounded automata

b.a push down automata

c. a deterministic push down automata

d. a finite automata



Q12. Consider the following grammar

S---->bS|aA|b

A---->bA|aB

B--->bB|aS|a

Let Na(w) and Nb(w) denote the number of a's and b's in a string w. Then the language L(G) a subset of (a+b)+ generated by G is

A. {w| Na(w)>3Nb(w)}

B.{w|Nb(w)>3Na(w)}

C.{w|Na(w)=3k, k=0,1,2,...}

D.{w|Nb(w)=3k, k = 0,1,2,...} [GATE 2004]



Q13.. Consider the following grammar

S---->bS|aA|b

A---->bA|aB

B--->bB|aS|a

Let Na(w) and Nb(w) denote the number of a's and b's in a string w in the reversal of the language. Then the language reversal of L(G) a subset of (a+b)+ generated by G is

A. {w| Na(w)>3Nb(w)}

B.{w|Nb(w)>3Na(w)}

C.{w|Na(w)=3k, k=0,1,2,...}

D.{w|Nb(w)=3k, k = 0,1,2,...}



Q14. Consider the following grammar

S---->Sb|Aa|b

A---->Ab|Ba

B--->Bb|Sa|a

Let Na(w) and Nb(w) denote the number of a's and b's in a string w. Then the language L(G) a subset of (a+b)+ generated by G is

A. {w| Na(w)>3Nb(w)}

B.{w|Nb(w)>3Na(w)}

C.{w|Na(w)=3k, k=0,1,2,...}

D.{w|Nb(w)=3k, k = 0,1,2,...}



Q15. Consider the following grammar

S---->bS|aA|b

A---->bA|aB

B--->bB|aS|a

The language generated by the grammar is

a. r.e but not recursive

b. recursive but not csl

c.csl but not cfl

d. regular but not finite



Q16. Consider the following grammar

S---->bS|aA|b

A---->bA|aB

B--->bB|aS|a

The grammar is

a. type-0 but not type-1

b. type-1 but not type-2

c. type-2 but not type-3

d. type-3



Q17. Consider the grammar

S--->AS|AA

A--->aAb|ab

Let Na(w) and Nb(w) denote the number of a's and b's in a string w. Then the language L(G) a subset of (a+b)+ generated by G is

A. {w| Na(w)>Nb(w)}

B.{w|Nb(w)<Na(w)}

C.{w|Na(w)=Nb(W)}

D.{w|Nb(w)not related to Na(w)}



Q18. Consider the grammar

S--->aSa|bSb|aa|bb



Let Na(w) and Nb(w) denote the number of a's and b's in a string w. Then the language L(G) a subset of (a+b)+ generated by G is

A. {w| Na(w)>Nb(w)}

B.{w|Nb(w)<Na(w)}

C.{w|Na(w)=Nb(W)}

D.{w|Nb(w)not related to Na(w)}



Q19. Consider the grammar

S--->aSa|bSb|aSb|bSa|aa|ab|ba|bb

Let Na(w) and Nb(w) denote the number of a's and b's in a string w. Then the language L(G) a subset of (a+b)+ generated by G is

A. {w| Na(w)>Nb(w)}

B.{w|Nb(w)<Na(w)}

C.{w|Na(w)=Nb(W)}

D.{w|Nb(w)not related to Na(w)}



Q20. Consider the grammar

S--->AB

A--->aAb|ab

B--->b|bB

Let Na(w) and Nb(w) denote the number of a's and b's in a string w. Then the language L(G) a subset of (a+b)+ generated by G is

A. {w| Na(w)>Nb(w)}

B.{w|Nb(w)<Na(w)}

C.{w|Na(w)=Nb(W)}

D.{w|Nb(w)not related to Na(w)}