544 views
2 votes
2 votes

$L_{1}=\left \{ 0^{m}.1^{n}.2^{m}.3^{n} \right |n,m>0\}$

$L_{2}=\left \{ a^{i}.b^{j}.c^{k}.d^{l} \right |i+k=j+l\}$

which one DCFL?

Refrence :https://gateoverflow.in/15327/context-free-or-not


I think both not DCFL, but need valid reason for it

1 Answer

2 votes
2 votes
1. First 1 is not CFL because it cannot be realised using a PDA. It's in fact a CSL langalan accepted by Turning machine.

2. Given condition i + k = j + l ;

It can be written as i - j =  l - k. Push all A's and Pop for every B's remaining is i - j in the stack. Similarly push all C's and Pop for every D remaining is l - k. It can be compared. It's a DCFL.

Please correct me if wrong..!

Related questions

0 votes
0 votes
0 answers
1
Na462 asked Sep 11, 2018
700 views
Consider the following languages :L1: {a bn a2n | n ≥ 0 }L2: { a a bn a3n | n ≥ 0 }Which of the following is true ?A. L1 U L2 is regularB. L1 U L2 is DCFLC. L1 inters...
4 votes
4 votes
1 answer
2
1 votes
1 votes
1 answer
3
1 votes
1 votes
2 answers
4
ggwon asked Dec 29, 2022
703 views
L = {$a^{n+m}b^{n}a^{m} | n,m \geq 0$}Is the above language DCFL or CFL ?