Context Free Grammars Questions

MCQ bookmark_border

51.

Grammars that can be translated to DFAs is ___________

A

Left linear grammar

B

Right linear grammar

C

Generic grammar

D

All of the mentioned

Correct Answer: B

Right linear grammar can be translated to the DFAs.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

52.

Which of the following language accepted by a Push down Automata?

A

Type0

B

Type1

C

Type2

D

Type3

Correct Answer: C

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

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

53.

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

Correct Answer: B

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

54.

Push down automata accepts which language

A

 Context sensitive language

B

Context free language

C

Recursive language

D

None of these

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

55.

Which of the following statement is false?

A

A recursive language is also a regular language

B

 A context free language is also a regular language

C

 A context free language is also recursive enumerable language

D

Both (a) and (b)

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

56.

Which of the following statement is false?

A

The context free language can be converted into Chomsky normal form

B

The context free language can be converted into Greibach normal form

C

 The context free language is accepted by pushdown automata

D

None of these

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

57.

The language L={0?1?0?| m ? 1} is a

A

Regular language

B

Context free language

C

 Both (a) and (b)

D

None of these

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

58.

While converting the context free grammar into Greibach normal form, which of the following is not necessary

A

Elimination of null production

B

Elimination of unit production

C

 Converting given grammar in Chomsky normal form

D

None of these

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

59.

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

A

 {0?1? | n=2, m=3}

B

  {0?1? | n=1, m=5}

C

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

D

 None of these

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

60.

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

A

 Equal number of 0

B

Unequal number of 0

C

Any number of 0

D

None of these

Correct Answer: A

Check Answer report_problem Report forum Discussion