in Theory of Computation edited by
343 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$?
in Theory of Computation edited by
343 views

1 comment

the regular expression we are doing union is (a+b)*-(ɛ,a,b,ab) so union with dcfl it gives expression as (a+b)* -(ɛ,ab) so it is regular ….correct me if I missed something
0
0

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\}.$

Related questions