Context Free Grammars Questions

MCQ bookmark_border

11.

Consider a CFG with the following productions. S ? AA | B A ? 0A | A0 | 1 B ? 0B00 | 1 S is the start symbol, A and B are non-terminals and 0 and 1 are the terminals. The language generated by this grammar is

A

{0ⁿ 10²ⁿ | n ? 1}

B

{0ⁱ 10^j 10^k | i, j, k ? 0} ? {0ⁿ 10²ⁿ | n ? l}

C

{0ⁱ 10^j | i, j ? 0} ? {0ⁿ 10²ⁿ | n ? l}

D

The set of all strings over {0, 1} containing at least two 0's

E

None of the above

Correct Answer: E

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

12.

A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.
S?aS?A
A?aAb?bAa??
Which of the following strings is generated by the grammar above?

A

aabbaba

B

aabaaba

C

abababb

D

aabbaab

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

13.

A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.
S?aS?A
A?aAb?bAa??
For the correct answer in Q75, how many steps are required to derive the string and how many parse trees are there?

A

6 and 1

B

6 and 2

C

7 and 2

D

4 and 2

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

14.

Consider 2 scenarios:

C1: For DFA (?, ?, ?, qo, F),
         if F = ?, then L = ?*
C2: For NFA (?, ?, ?, qo, F),
         if F = ?, then L = ?*
Where F = Final states set
? = Total states set

Choose the correct option ?

A

Both are true

B

Both are False

C

C1 is true, C2 is false

D

C1 is false, C2 is true

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

15.

Let G be the CFG, l be the number of left most derivations, r be the number of right most derivations and P be the number of parse trees. Assume l , r and P are computed for a particular string. For a given CFG

A

l ? P ? r

B

l = P = r

C

l ? P ? r

D

none of these

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

16.

Context free languages are closed under-

A

Union, Intersection

B

Union, Kleene closure

C

Intersection, Complement

D

Complement, Kleene closure

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

17.

Let G be a context-free grammar where G = ( { S, A, B, C}, { a,b, d}, P, S ) with the productions in P given below.

S ? ABAC
A ? aA ? ?
B ? bB ? ?
C ? d

 (? denotes null string). Transform the grammar G to an equivalent context-free grammar G' that has no ? productions and no unit productions. (A unit production is of the form x ? y, and x and y are non terminals.)

A

the set of all binary strings with unequal number of 0's and 1's

B

the set of all binary strings including null string

C

the set of all binary strings with exactly one more 0 than the number of 1

D

None of the above

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

18.

Consider the following context-free grammar over the alphabet ? = {a, b} with S as the start symbol:

S ? AT 
A ? aAa | bAb | #T 
T ? aT | bT | ? 

Which of the following represents the language generated by the above grammar?

A

{ w#x | w^R is a substring of x, where w, x ? {a, b}* }

B

{ w#x | w is a substring of x, where w, x ? {a, b}* }

C

x#w | w^R is a substring of x, where w, x ? {a, b}* }

D

{ w#x | w, x ? {a, b}* }

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

19.

Consider the following context free languages:

L1 = {0^i 1^j 2^k | i+j = k}
L2 = {0^i 1^j 2^k | i = j or j = k}
L3 = {0^i 1^j  | i = 2j+1}

 Which of the following option is true?

A

L1, L2 and L3 can be recognized by Deterministic Push down automata

B

L1, L2 can be recognized by Deterministic Push down automata

C

L1, L3 can be recognized by Deterministic Push down automata

D

None of the above

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

20.

Which of the following language(s) generates more than one parse tree for a string ?

L1 = {a^nb^mc^md^n ? {a, b, c, d}* | n, m ? 0} 
      ? {a^nb^nc^md^m ? {a, b, c, d}* | n, m ? 0} 

L2 = {a^nb^mc^m ? {a, b, c}* | n, m ? 0} 
      ? {a^nb^nc^m ? {a, b, c}* | n, m ? 0}

L3 = {a^nb^mc^p ? {a, b, c}* | n ? m; n, m ? 0} 
      ? {a^nb^mc^p ? {a, b, c}* | m ? p; n, m ? 0}

A

Only L1 and L2

B

Only L1 and L3

C

Only L2 and L3

D

All L1, L2, and L3

Correct Answer: D

Check Answer report_problem Report forum Discussion