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.
Q202.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
Q203. 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
Q204. 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
Q205. 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
Q206. 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
Q207. 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
Q208. 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
Q209. 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
Q210. 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
Q211. 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
Q212. 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]
Q213.. 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,...}
Q214. 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,...}
Q215. 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
Q216. 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
Q217. 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)}
Q218. 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)}
Q219. 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)}
Q220. 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
