Regular and context free languages Questions

MCQ bookmark_border

21.

  

the reverse of the string w. Which of these languages are deterministic Context-free languages?

A

None of the languages

B

Only L1

C

Only L1 and L2

D

All the three languages

Correct Answer: C

For L1 and L2 we can design Deterministic Push down automata, so both are DCFL. But for L3, it is not possible to design deterministic PDA, because DPDA cannot determine where 'w' ends exactly so it could start poping symbols (for wr ) from the stack. Therefore, option (C) is Correct.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

22.

Which of these languages are not context free

A

L1 only

B

L3 Only

C

L1 and L2

D

L2 and L3

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

23.

In the correct grammar of above question, what is the length of the derivation (number of steps starring from S) to generate the string a^lb^m with l ? m? 

A

max(l,m) + 2

B

l + m + 2

C

l + m + 3

D

max(l, m) + 3

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

24.

Consider the languages:

L1 = {anbncm | n, m > 0} 
L2 = {anbmcm | n, m > 0} 

Which one of the following statements is FALSE?

A

L1 ? L2 is a context-free language

B

L1 U L2 is a context-free language

C

L1 and L2 are context-free language

D

L1 ? L2 is a context sensitive language

Correct Answer: A

We can recognize strings of given language using one Stack. These given languages are context free, so also context sensitive. Because CFLs are closed under Union property, so union of given languages will also be Context free. But CFLs are not closed under Intersection property, so Intersection of two CFLs may not be CFL. Given L1 and If L2 are two context free languages, their intersection L1 ? L2 is not context free because we cannot identify strings of resultant language with help of one Stack: L1 = { anbncm | n > 0 and m > 0 } and L2 = { ambncn | n > 0 and m > 0 } L3 = L1 ? L2 = { anbncn | n > 0 } is not context free. So, option (a) is false. See wikipedia page for closure properties.

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

25.

Consider the languages:

L1 = {wwR |w ? {0, 1}*}
L2 = {w#wR | w ? {0, 1}*}, where # is a special symbol
L3 = {ww |  w ?  (0, 1}*)

 Which one of the following is TRUE?

A

L1 is a deterministic CFL

B

L2 is a deterministic CFL

C

L3 is a CFL, but not a deterministic CFL

D

L3 is a deterministic CFL

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

26.

The language {am bn Cm+n | m, n ? 1} is

A

regular

B

context-free but not regular

C

context sensitive but not context free

D

type-0 but not context sensitive

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

27.

If the strings of a language L can be effectively enumerated in lexicographic (i.e., alphabetic) order, which of the following statements is true ?

A

L is necessarily finite

B

L is regular but not necessarily finite

C

L is context free but not necessarily regular

D

L is recursive but not necessarily context free

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

28.

Let G = ({S}, {a, b} R, S) be a context free grammar where the rule set R is S ? a S b | SS | ? Which of the following statements is true?

A

G is not ambiguous

B

There exist x, y, ? L (G) such that xy ? L(G)

C

There is a deterministic pushdown automaton that accepts L(G)

D

We can find a deterministic finite state automaton that accepts L(G)

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

29.

Consider the following languages:
I. {ambncpdq ? m + p = n + q, where m, n, p, q ? 0}
II. {ambncpdq ? m = n and p = q, where m, n, p, q ? 0}
III. {ambncpdq ? m = n = p and p ? q, where m, n, p, q ? 0}
IV. {ambncpdq ? mn = p + q, where m, n, p, q ? 0}
Which of the above languages are context-free?

A

I and IV only

B

I and II only

C

II and III only

D

II and IV only

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

30.

Consider the grammar with productionsS ? aSb | SS | ?This grammar is

A

not context-free, not linear

B

not context-free, linear

C

context-free, not linear

D

context free, linear

Correct Answer: C

Check Answer report_problem Report forum Discussion