Context Free Grammars Questions

MCQ bookmark_border

1.

Which of the following pairs have DIFFERENT expressive power?

A

Deterministic finite automata(DFA) and Non-deterministic finite automata(NFA)

B

Deterministic push down automata(DPDA)and Non-deterministic push down automata(NPDA)

C

Deterministic single-tape Turing machine and Non-deterministic single-tape Turing machine

D

Single-tape Turing machine and multi-tape Turing machine

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

2.

Assume Statement 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 Turnig machine is countable. Which of the following is true?

A

S1 is correct ans 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: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

3.

A context free language is called ambigous if ______________

A

it has 2 or more left derivations for some terminal string w e L(G)

B

it has 2 more or more right derivations for some terminal string w e L(G)

C

it has two or more left & right derivations for some terminal string w e L(G)

D

None of the mentioned

Correct Answer: B

A context-free grammer (CFG) is a set of recursive rewriting rules (or productions) use to generate pattern of strings.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

4.

Which of the following  statement is false ?

A

The CFG can be converted to Chomsky normal form

B

The CFG can be converted to Greibach normal form

C

CFG is accepted by pushdown automata

D

None of the mentioned

Correct Answer: D

All the statement follow the rules

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

5.

The context free grammer S->SS | oS1 | 1So |  e generates

A

Equal number of O's and 1's

B

Unequal number of O's and 1's

C

Number of O's followd by any number of 1's

D

None of the mentioned

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

6.

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 variables

C

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

D

None of the mentioned

Correct Answer: D

All of them are true regarding a derivation true

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

7.

Push down automata excepts which language ?

A

Context Sensitive Language

B

Context free Language

C

Recursive Language

D

None of the mentioned

Correct Answer: B

PDA excepts of CFG

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

8.

A regular Grammer is a ___________

A

CFG

B

Non CFG

C

English Grammer

D

None of the mentioned

Correct Answer: A

Regular grammer is CFG. It restricts its rules to a single non terminal on left hand side

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

9.

A CFG is close under ________

A

Union

B

Kleene star

C

Concatenation

D

None of the mentioned

Correct Answer: D

CFG is close under the above mentioned 3 operations

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

10.

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