Test: Context Free Grammar

I accept the Terms & Conditions.

Description

This mock test of Test: Context Free Grammar for Computer Science Engineering (CSE) helps you for every Computer Science Engineering (CSE) entrance exam. This contains 10 Multiple Choice Questions for Computer Science Engineering (CSE) Test: Context Free Grammar (mcq) to study with solutions a complete question bank. The solved questions answers in this Test: Context Free Grammar quiz give you a good mix of easy questions and tough questions. Computer Science Engineering (CSE) students definitely take this Test: Context Free Grammar exercise for a better result in the exam. You can find other Test: Context Free Grammar extra questions, long questions & short questions for Computer Science Engineering (CSE) on EduRev as well by searching above.

QUESTION: 1

Assume the statements S1 and S2 given as:
S1: Given a context free grammar, there exists an algorithm for determining whether L (G) is infinite.
S2: There exists an algorithm to determine whether two context free grammars generate the same language.
Which of the following is true?

A.
S1 is correct and S2 is not correct
B.
Both S1 and S2 are correct
C.
Both S1 and S2 are not correct
D.
S1 is not correct and S2 is correct

Solution:

The proof of S1 can be seen in various book of theory of computation but s2 is a problem of category undecidable so a contradiction to this assumption can be easily obtained.

QUESTION: 2

If P & R are regular and also given that if PQ=R, then

A.
Q has to be regular
B.
Q cannot be regular
C.
Q need not be regular
D.
Q has to be a CFL

Solution:

If two regular languages when combined do not always produce a regular language.

QUESTION: 3

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

Solution:

Not every NDPDA has an equivalent deterministic PDA.

QUESTION: 4

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.
< > > >

Solution:

This relation is established of basis of the precedence of operators.

QUESTION: 5

Recursively enumerable languages are not closed under:

A.
Union
B.
Intersection
C.
Complementation
D.
Concatenation

Solution:

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.

QUESTION: 6

Grammar that produce more than one Parse tree for same sentence is:

A.
Ambiguous
B.
Unambiguous
C.
Complementation
D.
Concatenation Intersection

Solution:

an ambiguous grammar is one for which there is more than one parse tree for a single sentence.

QUESTION: 7

Automaton accepting the regular expression of any number of a ‘ s is:

A.
a*
B.
ab*
C.
(a/b)*
D.
a*b*c

Solution:

It gives any number of a’s.

QUESTION: 8

Grammars that can be translated to DFAs:

A.
Left linear grammar
B.
Right linear grammar
C.
Generic grammar
D.
All of the mentioned

Solution:

Right linear grammar can be translated to the DFAs.

QUESTION: 9

The language accepted by a Push down Automata:

A.
Type0
B.
Type1
C.
Type2
D.
Type3

Solution:

A known fact that type 2 grammar is accepted by PDA.

QUESTION: 10

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

Solution:

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.