Regular and context free languages Questions

MCQ bookmark_border

41.

Let G = (V, T, S, P) be a context-free grammar such that every one of its productions is of the form A ? v, with |v| = K > 1. The derivation tree for any W ? L(G) has a height h such that

A

logK|W| ? h ? logK((|W|-1)/k-1)

B

logK|W| ? h ? logK(K|W|)

C

logK|W| ? h ? K logK|W|

D

logK|W| ? h ? ((|W|-1)/k-1)

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

42.

Given the following two languages : L1 = {an bn | n ? 0, n ? 100} L2 = {w ? {a, b, c}*| na(w) = nb(w) = nc(w)} Which of the following options is correct ?

A

Both L₁ and L₂ are not context free language

B

Both L₁ and L₂ are context free language.

C

L₁ is context free language, L₂ is not context free language.

D

L₁ is not context free language, L₂ is context free language

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

43.

Given the following two statements : A. L = {w|n_a(w) = n_b(w)} is deterministic context free language, but not linear. B. L = {aⁿ bⁿ} ? {aⁿ b²ⁿ} is linear, but not deterministic context free language. Which of the following options is correct ?

A

Both (A) and (B) are false

B

Both (A) and (B) are true

C

(A) is true, (B) is false.

D

(A) is false, (B) is true

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

44.

What is the number of steps required to derive the string ((() ()) ())

S ? SS
S ? (S)
S ? ?

A

10

B

15

C

12

D

16

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

45.

Consider the following grammar.

S -> AB
A -> a
A -> BaB
B -> bbA

Which of the following statements is FALSE?

A

The length of every string produced by this grammar is even

B

No string produced by this grammar has three consecutive a's

C

The length of substring produced by B is always odd

D

No string produced by this grammar has four consecutive b's

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

46.

Let L = {0ⁿ1ⁿ|n ? 0} be a context free language. Which of the following is correct ?

A

L` is context free and L^k is not context free for any k ? 1.

B

L` is not context free and L^k is not context free for any k ? 1

C

Both L` and L^k is for any k ? 1 are context free.

D

Both L` and L^k is for any k ? 1 are not context free

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

47.

Given a Turing Machine M = ({q0, q1, q2, q3}, {a, b}, {a, b, B}, ?, B, {q3}) Where ? is a transition function defined as ?(q0, a) = (q1, a, R) ?(q1, b) = (q2, b, R) ?(q2, a) = (q2, a, R) ?(q3, b) = (q3, b, R) The language L(M) accepted by the Turing Machine is given as:

A

aa*b

B

abab

C

aba*b

D

aba*

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

48.

Match the following:

A

1

B

2

C

3

D

4

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

49.

The language of all non-null strings of a

A

two

B

three

C

four

D

five

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

50.

If all the production rules have single non - terminal symbol on the left side, the grammar defined is:

A

context free grammar

B

context sensitive grammar

C

unrestricted grammar

D

phrase grammar

Correct Answer: A

Check Answer report_problem Report forum Discussion