Question 41 : Which of the following statement is false?
1. The CFG can be converted to Chomsky normal form
2. The CFG can be converted to Greibach normal form
3. CFG is accepted by pushdown automata
4. None of the mentioned
View Answer   Discuss with Members

Question 42 : A context free language is called ambiguous if
1. It has 2 or more left derivations for some terminal string ? ? L (G)
2. It has 2 or more right derivations for some terminal string ? ? L (G)
3. Both of the mentioned
4. None of the mentioned
View Answer   Discuss with Members

Question 43 : Assume statements S1 and S2 defined as: S1: L2-L1 is recursive enumerable where L1 and L2 are recursive and recursive enumerable respectively. S2: The set of all Turing machines is countable. Which of the following is true?
1. S1 is correct and S2 is not correct
2. Both S1 and S2 are correct
3. Both S1 and S2 are not correct
4. S1 is not correct and S2 is correct
View Answer   Discuss with Members

Question 44 : 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?
1. I only
2. II only
3. Both I and II
4. Neither I nor II
View Answer   Discuss with Members

Question 45 : The language accepted by a Push down Automata:
1. Type0
2. Type1
3. Type2
4. Type3
View Answer   Discuss with Members

Question 46 : Grammars that can be translated to DFAs:
1. Left linear grammar
2. Right linear grammar
3. Generic grammar
4. All of the mentioned
View Answer   Discuss with Members

Question 47 : Grammar that produce more than one Parse tree for same sentence is:
1. Ambiguous
2. Unambiguous
3. Complementation
4. Concatenation Intersection
View Answer   Discuss with Members

Question 48 : Recursively enumerable languages are not closed under:
1. Union
2. Intersection
3. Complementation
4. Concatenation
View Answer   Discuss with Members

Question 49 : 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
1. All <
2. All >
3. < > , =
4. < > > >
View Answer   Discuss with Members

Question 50 : Which of the following conversion is not possible (algorithmically)?
1. Regular grammar to CFG
2. NDFA to DFA
3. NDPDA to DPDA
4. NDTM to DTM
View Answer   Discuss with Members