8,845 views
36 votes
36 votes

Consider the following languages.

  • $L_1 = \{a^p \mid p \text{ is a prime number} \}$
  • $L_2 = \{ a^nb^mc^{2m} \mid n \geq 0, m \geq 0 \}$
  • $L_3 = \{a^n b^n c^{2n} \mid n \geq 0 \}$
  • $L_4 = \{ a^n b^n \mid n \geq 1\}$

Which of the following are CORRECT?

  1. $L_1$ is context free but not regular
  2. $L_2$ is not context free
  3. $L_3$ is not context free but recursive
  4. $L_4$ is deterministic context free
  1. I, II and IV only
  2. II and III only
  3. I and IV only
  4. III and IV only

4 Answers

Best answer
36 votes
36 votes

$L_1$ is Csl, $L_2$ is context free

$L_3$ is not Context free and $L_4$ is Dcfl

So, option is D.

edited by
29 votes
29 votes

L1 : {aa,aaa,aaaaa,aaaaaa,......}.It is CSL because prime numbers does not have a fixed pattern.

L2 : push a push b then pop one b for each 2 c's and accept it when top of stack has a.It is DCFL.

L3: for a and b then for b and c two comparisons and therefore two stacks are required .It is CSL.

L4 : Classical example of DCFL. Push a then pop a for each b.

Options 

I. wrong because L1 is not CFL. 

II. wrong because L2 is DCFL so it is CFL .

III. Right because every CSL is Recursive but not CFL.

IV. Right it is DCFL.

Since III and IV are only correct options Ans is D.

Answer:

Related questions

77 votes
77 votes
12 answers
2
Arjun asked Feb 14, 2017
28,050 views
Let $\delta$ denote the transition function and $\widehat{\delta}$ denote the extended transition function of the $\epsilon$-NFA whose transition table is given below:$$\...