in Theory of Computation ago edited ago by
23 views
0 votes
0 votes
$L=\{a^mb^n∣m≠n\}∪{(a+b)^∗b(b+a)^*a(a+b)^∗}=\{a^mb^n|m<n\} \cup \{a^mb^n|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 made DPDA for $L$?
in Theory of Computation ago edited ago by
by
2 2 5
23 views

Subscribe to GO Classes for GATE CSE 2022

1 Answer

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

Related questions