Theory of Computation and Compilers MCQ - Context free languages

11 Define for the context free language
L< {0;1} init (L) = { u | u v ε L for some v in {0, 1}}
If L { w | w is nonempty and has an equal number of 0's and 1's}, then init (L) is set of all binary strings

A
with unequal numbers of 0's and 1's.
B
including the null string.
C
Both (a) and (b)
D
None of these

View Explanation
Comment

Correct AnswerOption B

Rate difficulty Rate difficulty:

Easy Medium Hard

Choose a difficulty.

Cancel reply

Your email address will not be published. Required fields are marked *

Report

Name

Save my name and email in this browser for the next time I comment.

Cancel reply

Your email address will not be published. Required fields are marked *

Comment *

Name

Save my name and email in this browser for the next time I comment.

12 Which of the following CFG's can't be simulated by an FSM?

A
s ---> sa | a
B
s ---> abX , X --> cY, Y --> a | axY
C
s ---> a sb | ab
D
none of these

View Explanation
Comment

Correct AnswerOption C

Rate difficulty Rate difficulty:

Easy Medium Hard

Choose a difficulty.

Found this useful?

Follow:

Cancel reply

Your email address will not be published. Required fields are marked *

Report

Name

Save my name and email in this browser for the next time I comment.

Cancel reply

Your email address will not be published. Required fields are marked *

Comment *

Name

Save my name and email in this browser for the next time I comment.

13 Basic limitation of FSM is that it

A
cannot remember arbitrary large amount of information
B
sometimes fails to recognize grammars that are regular
C
sometimes recognizes grammars are not regular
D
None of these

View Explanation
Comment

Correct AnswerOption A

Rate difficulty Rate difficulty:

Easy Medium Hard

Choose a difficulty.

Cancel reply

Your email address will not be published. Required fields are marked *

Report

Name

Save my name and email in this browser for the next time I comment.

Cancel reply

Your email address will not be published. Required fields are marked *

Comment *

Name

Save my name and email in this browser for the next time I comment.

14 Which of the following is not possible algorithmically?

A
Regular grammar to context free grammar
B
Non-deterministic FSA to deterministic FSA
C
Non-deterministic PDA to deterministic PDA
D
None of these

View Explanation
Comment

Correct AnswerOption C

Rate difficulty Rate difficulty:

Easy Medium Hard

Choose a difficulty.

Cancel reply

Your email address will not be published. Required fields are marked *

Report

Name

Save my name and email in this browser for the next time I comment.

Cancel reply

Your email address will not be published. Required fields are marked *

Comment *

Name

Save my name and email in this browser for the next time I comment.

15 The set {aⁿbⁿ | n = 1, 2, 3 ...} can be generated by the CFG

A
S → ab | aSb
B
S → aaSbb + abS
C
S → ab | aSb | E
D
S → aaSbb | ab | aabb

View Explanation
Comment

Correct AnswerOption D

Rate difficulty Rate difficulty:

Easy Medium Hard

Choose a difficulty.

Option (B) is wrong because it can't generate aabb (in fact any even power).
Option (C) is wrong since it generates E also.
Both options (A) and (D) are correct.

Cancel reply

Your email address will not be published. Required fields are marked *

Report

Name

Save my name and email in this browser for the next time I comment.

Cancel reply

Your email address will not be published. Required fields are marked *

Comment *

Name

Save my name and email in this browser for the next time I comment.

First Previous 1 2 3 4 5 Next Last