in Theory of Computation
6,496 views
29 votes
29 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
in Theory of Computation
by
51 95 101
6.5k views

3 Comments

Explain L2 and L3 please
0
0
can anyone pls tell me why l3 is not cfl
0
0

Make a PDA for that language or try to write grammar. The problem is after verifying #a=#b, the same number has to be ½ of #c, which cannot be verified as the stack will be empty.

1
1

Subscribe to GO Classes for GATE CSE 2022

4 Answers

30 votes
30 votes
 
Best answer

$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
by
5 14 22

3 Comments

Please explain how L1 is a CSL?
I'm not able to imagine how L1 could be accepted by LBA which has limited tape.
0
0
1
1
5
5
25 votes
25 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.

by
9 33 67

3 Comments

@Ravi_1511 Brother, in L2 = can I push 2 "b's" for one b and pop single "b" for every "c"

0
0

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

This statement makes it a much accurate answer than the best answer

0
0

@Ravi_1511 @Arjun Sir, @Bikram Sir  , Pls check my understanding:

For L3, we needed two comparisons back-to-back on the same variable(n).

Thats why it is not CFL.

But, If we see 1 in this problem ,

https://gateoverflow.in/204109/gate2018-35

We needed 2 comparisons too, but on different variables.

Thats why that problem was CFL, & this problem is not CFL

0
0
0 votes
0 votes
option d is correct
by
1 1 1
0 votes
0 votes

answer is D

by
1 2 7
Answer:

Related questions