0 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$? Theory of Computation dcfl context-free-language theory-of-computation + – juuniversity 730 views answer comment Share Follow Print See 1 comment 1 1 comment reply Kishor_1403 commented Nov 8, 2023 reply Follow flag 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 replyShare Please log in or register to add a comment.
Best answer 1 1 vote $L$ is equivalent to $(a+b) ^*-\{a^nb^n\}$ which is well known DCFL, I mean $L$ is complement of $\{a^nb^n\}.$ juuniversity answered Jun 24, 2022 juuniversity comment Share Follow 0 reply Please log in or register to add a comment.