Regular and context free languages Questions

MCQ bookmark_border

31.

Identify the language generated by the following grammar

S -> AB
 A -> aAb|?
 B -> bB| b 

A

{a^mbⁿ | n>=m, m>0}

B

{a^mbⁿ | n>=m, m>=0}

C

{a^mbⁿ | n>m, m>0}

D

{a^mbⁿ | n>m, m>=0}

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

32.

Let L1 be regular language, L2 be a deterministic context free language and L3 a recursively enumerable language, but not recursive. Which one of the following statements is false?

A

L3 ? L1 is recursive

B

L1 ? L2 ? L3 is recursively enumerable

C

L1 ? L2 is context free

D

L1 ? L2 is context free

Correct Answer: A

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

33.

Which of the following are context free?

A = {anbnambm | m, n>=0}
B = {ambnambn | m, n>=0}
C = {ambn | m?2n,m, n>=0}

A

A and B only

B

A and C only

C

B and C only

D

C only

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

34.

The language L = {aⁱb cⁱ ? i >= 0} over the alphabet {a, b, c} is:

A

a regular language.

B

not a deterministic context free language but a context free language.

C

recursive and is a deterministic context free language

D

not recursive

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

35.

Context free grammar is not closed under:

A

Concatenation

B

Complementation

C

Kleene Star

D

Union

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

36.

Consider the following languages: L1 = {am bn ? m ? n} L2 = {am bn ? m = 2n+1} L3 = {am bm ? m ? 2n} Which one of the following statement is correct ?

A

Only L₁ and L₂ are context free languages

B

Only L₁ and L₃ are context free languages

C

Only L₂ and L₃ are context free languages

D

L₁, L₂ and L₃ are context free languages

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

37.

Which one of the following is FALSE?

A

There is a unique minimal DFA for every regular language

B

Every NFA can be converted to an equivalent PDA

C

Compliment of every context-free language is recursive

D

Every non-deterministic PDA can be converted to an equivalent deterministic PDA

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

38.

Consider the following statements about the context free grammar G = {S-->SS , S-->ab , S-->ba , S-->^} I. G is ambiguous II. G produces all strings with equal number of a

A

I only

B

I and III only

C

II and III only

D

I, II and III

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

39.

Consider the languages L1 = ? and L2 = {1}. Which one of the following represents L*₁? L*₁ L*₂ ?

A

{?}

B

{?, 1}

C

?

D

1*

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

40.

Given the following statements : (A) A class of languages that is closed under union and complementation has to be closed under intersection. (B) A class of languages that is closed under union and intersection has to be closed under complementation. 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: C

Check Answer report_problem Report forum Discussion