Regular and context free languages Questions

MCQ bookmark_border

51.

The context free grammar given by S ? XYX X ? aX|bX|? Y ? bbb generates the language which is defined by regular expression:

A

(a + b)*bbb

B

abbb(a + b)*

C

(a + b)*(bbb)(a + b)*

D

(a + b)(bbb)(a + b)*

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

52.

Given the following two languages: L1 = {anban|n > 0} L2 = {an b an bn + 1|n > 0} Which of the following is correct ?

A

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

B

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

C

Both L₁ and L₂ are context free languages

D

Both L₁ and L₂ are not context free languages

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

53.

Which variable does not drive a terminal string in grammar? S -> AB A -> a B -> b B -> C

A

A

B

B

C

C

D

D

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

54.

Which of the following sentences can be generated by

S -> aS | bA
A -> d | cA

A

bccdd

B

abbcca

C

abcabc

D

abcd

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

55.

Given the following grammars: G₁: S ? AB|aaB A ? aA | ? B ? bB | ? G₂: S ? A|B A ? aAb | ab B ? abB | ? Which of the following is correct?

A

G ₁ is ambiguous and G ₂ is unambiguous grammars

B

G ₁ is unambiguous and G ₂ is ambiguous grammars

C

both G ₁ and G ₂ are ambiguous grammars

D

both G ₁ and G ₂ are unambiguous grammars

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

56.

The following Context-Free Grammar (CFG): S ? aB | bA A ? a | aS | bAA B ? b | bS | aBB will generate (1) odd numbers of a

A

(1)

B

(2) an (3)

C

(1), (2) and (3)

D

All are correct

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

57.

The following Context-Free Grammar (CFG): S ? aB | bA A ? a | aS | bAA B ? b | bS | aBB will generate (1) odd numbers of a

A

(1)

B

(2) an (3)

C

(1), (2) and (3)

D

All are correct

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

58.

The pushdown automation M = ({q0, q1, q2 }, {a, b}, {0, 1}, ?, q0 , 0, {q0}) with ? (q0, a, 0) = {q1 , 10} ? (q1, a, 1) = {q1 , 11} ? (q1, b, 1) = {q2 , ?} ? (q2, b, 1) = {q2 , ?} ? (q2, ?, 0) = {q0 , ?} Accepts the language

A

L = {a ⁿ b ^m | n, m ? 0}

B

L = {a ⁿ b ⁿ | n ? 0}

C

L = {a ⁿ b ^m | n, m ? 0}

D

L = {a ⁿ b ⁿ | n > 0}

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

59.

Match the following:

List - I	List - II
(a) Context free grammar	(i)Linear bounded automaton
(b) Regular grammar	(ii) Pushdown automaton
(c)Context sensitive grammar	(iii) Turing machine
(d)Unrestricted grammar	(iv)Deterministic finite automaton

codes:

	(a)	(b)	(c)	(d)
(A)	(ii)	(iv)	(iii)	(i)
(B)	(ii)	(iv)	(i)	(iii)
(C)	(iv)	(i)	(ii)	(iii)
(4)	(i)	(iv)	(iii	(ii)

A

A

B

B

C

C

D

D

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

60.

According to pumping lemma for context free languages: Let L be an infinite context free language, then there exists some positive integer m such that any w ? L with | w | ? m can be decomposed as w = u v x y z

A

with | vxy | ? m such that uv i xy i z ? L for all i = 0, 1, 2

B

with | vxy | ? m, and | vy | ? 1, such that uv ⁱ xy ⁱz ? L for all i = 0, 1, 2,

C

with | vxy | ? m, and | vy | ? 1, such that uv ⁱ xy ⁱz ? L for all i = 0, 1, 2

D

with | vxy | ? m, and | vy | ? 1, such that uv ⁱxy ⁱz ? L for all i = 0, 1, 2,

Correct Answer: B

Check Answer report_problem Report forum Discussion