Regular and context free languages Questions

MCQ bookmark_border

11.

Consider the following languages. 

Which one of the following statements is FALSE?

A

L2 is context-free

B

L1 intersection L2 is context-free.

C

Complement of L2 is recursive.

D

Complement of L1 is context-free but not regular.

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

12.

Which of the following pairs have DIFFERENT expressive power?

A

Deterministic finite automata(DFA) and Non-deterministic finite automata(NFA)

B

Deterministic push down automata(DPDA)and Non-deterministic push down automata(NPDA)

C

Deterministic single-tape Turing machine and Non-deterministic single-tape Turing machine

D

Single-tape Turing machine and multi-tape Turing machine

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

13.

 Consider the language L1,L2,L3 as given below. L1={0^{p}1^{q} | p,q \in N} L2={0^{p}1^{q} | p,q \in N and p=q} L3={0^{p}1^{q}0^{r} | p,q,r \in N and p=q=r} Which of the following statements is NOT TRUE?

A

Push Down Automata (PDA) can be used to recognize L1 and L2

B

L1 is a regular language

C

All the three languages are context free

D

Turing machine can be used to recognize all the three languages

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

14.

Let P be a regular language and Q be context-free language such that Q 	\subseteq P. (For example, let P be the language represented by the regular expression p*q* and Q be {pnqn|n \in N}). Then which of the following is ALWAYS regular?

A

(A) P \cap Q 

B

P - Q

C

\sum* - P

D

\sum* - Q

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

15.

Consider the languages L1 = {0ⁱ1^j | i != j}. L2 = {0ⁱ1^j | i = j}. L3 = {0ⁱ1^j | i = 2j+1}. L4 = {0ⁱ1^j | i != 2j}.

A

Only L2 is context free

B

Only L2 and L3 are context free

C

Only L1 and L2 are context free

D

All are context free

Correct Answer: D

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

16.

S -> aSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of

A

All palindromes

B

All odd length palindromes

C

Strings that begin and end with the same symbol

D

All even length palindromes

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

17.

Let L = L1?L2, where L1 and L2 are languages as defined below:

L1 = {a^{m}b^{m}ca^{n}b^{n} | m, n >= 0 }
L2 = {a^{i}b^{j}c^{k} | i, j, k >= 0 }
Then L is

A

Not recursive

B

Regular

C

Context free but not regular

D

Recursively enumerable but not context free

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

18.

The language L= {0ⁱ21ⁱ | i?0 } over the alphabet {0,1, 2} is:

A

not recursive

B

is recursive and is a deterministic CFL

C

is a regular language.

D

is not a deterministic CFL but a CFL

Correct Answer: B

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

19.

Consider the CFG with {S,A,B) as the non-terminal alphabet, {a,b) as the terminal alphabet, S as the start symbol and the following set of production rules

S --> aB        S --> bA
B --> b         A --> a
B --> bS        A --> aS
B --> aBB       A --> bAA
Which of the following strings is generated by the grammar?

A

aaaabb

B

aabbbb

C

aabbab

D

abbbba

Correct Answer: C

Check Answer report_problem Report forum Discussion

MCQ bookmark_border

20.

For the correct answer strings to above question, how many derivation trees are there?

A

1

B

2

C

3

D

4

Correct Answer: B

Check Answer report_problem Report forum Discussion