Context Free Grammars Questions

MCQ bookmark_border

36.

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?

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: B

The assumptions of statement S1 and S2 are correct.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

37.

A context free language is called ambiguous if _________

A

It has 2 or more left derivations for some terminal string ? ? L (G)

B

It has 2 or more right derivations for some terminal string ? ? L (G)

C

It has 2 or more left & right derivations for some terminal string ? ? L (G)

D

None of the mentioned

Correct Answer: B

A context-free grammar (CFG) is a set of recursive rewriting rules (or productions) used to generate patterns of strings.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

38.

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

CFG is accepted by pushdown automata

Correct Answer: D

All the statements follow the rules.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

39.

The context free grammar S ? A111|S1, A ? A0 | 00 is equivalent to _________

A

{0ⁿ1^m | n=2, m=3}

B

{0ⁿ1^m | n=1, m=5}

C

{0ⁿ1^m | n should be greater than two and m should be greater than four}

D

None of the mentioned

Correct Answer: A

S-> A111 S->00111 (A->00).

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

40.

The context free grammar S ? A111|S1, A ? A0 | 00 is equivalent to _________

A

{0ⁿ1^m | n=2, m=3}

B

{0ⁿ1^m | n=1, m=5}

C

{0ⁿ1^m | n should be greater than two and m should be greater than four}

D

None of the mentioned

Correct Answer: A

S-> A111 S->00111 (A->00).

Check Answer report_problem Report forum Discussion