1. Which of the following conversion is not possible (algorithmically)?
a) Regular grammar to CFG
b) NDFA to DFA
c) NDPDA to DPDA
d) NDTM to DTM
Explanation: Not every NDPDA has an equivalent deterministic PDA.
2. Consider the grammar given below E? E+E | E*E | E-E | E/E | E^E | (E) | id Assume that + and ^ have the same but least precedence, * and / have the next higher precedence but the same precedence and finally ^ has the highest precedence. Assume + and ^ associate to the left like * and / and that ^ associates to the right. Choose the correct for the ordered pairs (^,^), (-,-), (+,+), (*,*) in the operator precedence table constructed for the grammar.
a) All <
b) All >
c) < >, =
d) < > > >
Explanation: This relation is established of basis of the precedence of operators.
3. Recursively enumerable languages are not closed under ______________
a) Union
b) Intersection
c) Complementation
d) Concatenation
Explanation: Recursive languages are closed under the following operations.
The Kleene star L * of L
the concatenation L * o P of L and P
the union L U P
the intersection L ∩ P.
4. Grammar that produce more than one Parse tree for same sentence is ___________
a) Ambiguous
b) Unambiguous
c) Complementation
d) Concatenation Intersection
Explanation: An ambiguous grammar is one for which there is more than one parse tree for a single sentence.
5. Automaton accepting the regular expression of any number of a’ s is ___________
a) a*
b) ab*
c) (a/b)*
d) a*b*c
Explanation: It gives any number of a’s.
6. Grammars that can be translated to DFAs is ___________
a) Left linear grammar
b) Right linear grammar
c) Generic grammar
d) All of the mentioned
Explanation: Right linear grammar can be translated to the DFAs.
7. Which of the following language accepted by a Push down Automata?
a) Type0
b) Type1
c) Type2
d) Type3
Explanation: A known fact that type 2 grammar is accepted by PDA.
8. Given the following statements: (i) Recursive enumerable sets are closed under complementation. (ii) Recursive sets are closed under complements. Which is/are the correct statements?
a) I only
b) II only
c) Both I and II
d) Neither I nor II
Explanation: Recursive languages are closed under the following operations.
The Kleene star L * of L
The concatenation L * o P of L and P
The union L U P
The intersection L ∩ P.
9. How many strings of length less than 4 contains the language described by the regular expression (x+y)*y(a+ab)*?
a) 7
b) 10
c) 12
d) 11
Explanation: String of length 0 = 1
string of length 1 = 4
string of length 2 = 3
string of length 3 = 3.
10. Which of the following is true?
a) (01)*0 = 0(10)*
b) (0+1)*0(0+1)*1(0+1) = (0+1)*01(0+1)*
c) (0+1)*01(0+1)*+1*0* = (0+1)*
d) All of the mentioned
Explanation: All of the mentioned