edited by
349 views
0 votes
0 votes
$L=\{a^mb^n\mid m≠n\}∪{(a+b)^∗b(b+a)^*a(a+b)^∗}$

$\implies L = \;\{a^mb^n\mid m<n\} \cup \{a^mb^n\mid m>n\} \cup  (a+b)^*b(a+b)^*a(a+b)^*$

 It is DCFL ∪ Regular, hence it should be DCFL, but not able to design DPDA, always it designed as NPDA.

Can anybody make a DPDA for $L$?
edited by

1 Answer

Best answer
1 votes
1 votes
$L$ is equivalent to $(a+b) ^*-\{a^nb^n\}$ which is well known DCFL, I mean $L$ is complement of $\{a^nb^n\}.$

Related questions

2 votes
2 votes
0 answers
1
sunil sarode asked Jan 19, 2018
1,769 views
Consider two languages LA and LB over Σ={a,b}.LA= {a^ib^ja^k | i,j,k ≥ 0 and j=i+k}LB= {b^ia^jb^k | i,j,k ≥ 0 and j=i+k} Then ( LA ∪ LB ) is : A DCFL but not regul...
4 votes
4 votes
2 answers
2
srestha asked Jun 22, 2018
1,611 views
$\left \{ a^{m+n}b^{m+n}c^{n}|m,n\geq 1 \right \}$$\left \{ a^{m+n}b^{m+n}c^{k} |m,n,k\geq 1\right \}$$\left \{ a^{m+n}b^{m+k}c^{n+k} |m,n,k\geq 1\right \}$Which one DCFL...
0 votes
0 votes
1 answer
3
shivangi5 asked Dec 2, 2017
878 views
Consider the following languages:L1={abna2n|n>=0}L2={aabna3n|n>=0}Why L1UL2 is DCFL please explain?
1 votes
1 votes
1 answer
4
Himanshu1 asked Nov 2, 2015
1,008 views
Give an example of Unambiguous CFL which is not DCFL .