Context Free Grammars Questions

MCQ bookmark_border

41.

The context free grammar S ? SS | 0S1 | 1S0 | ? generates _________

A

Equal number of 0

B

Unequal number of 0

C

Number of 0

D

None of the mentioned

Correct Answer: A

S->SS S->0S1S S->0S11S0 S->0110.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

42.

Which of the following statement is false?

A

In derivation tree, the label of each leaf node is terminal

B

In derivation tree, the label of all nodes except leaf nodes is a variable

C

In derivation tree, if the root of a sub tree is X then it is called

D

None of the mentioned

Correct Answer: D

All of them are true regarding a derivation tree.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

43.

Which of these does not belong to CFG?

A

Terminal Symbol

B

Non terminal Symbol

C

Start symbol

D

End Symbol

Correct Answer: D

CFG consists of terminal non terminal start symbol set of production rules but does not have an end symbol.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

44.

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

Correct Answer: A

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.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

45.

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

Correct Answer: C

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

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

46.

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

Correct Answer: C

Not every NDPDA has an equivalent deterministic PDA.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

47.

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

< > > >

Correct Answer: D

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

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

48.

Recursively enumerable languages are not closed under ______________

A

Union

B

Intersection

C

Complementation

D

Concatenation

Correct Answer: C

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.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

49.

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

A

Ambiguous

B

Unambiguous

C

Complementation

D

Concatenation Intersection

Correct Answer: A

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

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

50.

Automaton accepting the regular expression of any number of a

A

a*

B

ab*

C

(a/b)*

D

a*b*c

Correct Answer: A

It gives any number of a

Check Answer report_problem Report forum Discussion