How to construct DPDA for the following language $L=\{a,b\}^* \setminus a^nb^n \setminus b^na^n $

$L_1 = \{a,b\}^* \setminus a^nb^n =\{a^i b^j \, | \, i>j\}\,\cup\,\{a^i b^j\ \ | \ i<j\}\,\cup\,(a+b)^* b (a+b)^* a (a+b)^*$.

At this step I got stuck. What is next? How to express additional difference $b^na^n$?

  • $\begingroup$ We are looking to build an archive of knowledge that will be useful to others in the future. "Here is an exercise-style task, I have no idea how to start, can you solve it for me?" typically is not a good fit for this site. I suggest you refer to cs.stackexchange.com/q/18524/755, try to identify what is preventing you from solving it, generalize your difficulty, and ask a conceptual question that is likely to be useful to others (even if they aren't looking at exactly the same task as you). $\endgroup$
    – D.W.
    Jul 7 at 21:14
  • $\begingroup$ @D.W. Corrected, you can remove your downvote. $\endgroup$
    – cs_student
    Jul 7 at 21:48
  • $\begingroup$ @cs_student how is it corrected? "/" mean? $\endgroup$
    – S. M.
    Jul 7 at 21:58
  • $\begingroup$ @AlokMaity look closely. Second sentence and explanation after it. $\endgroup$
    – cs_student
    Jul 7 at 22:01
  • $\begingroup$ Please use standard notation for languages. $/ a^n b^n$ is not a standard notation you will find in a textbook. It appears to be some kind of shorthand; please avoid shorthand and use standard mathematical notation. $\endgroup$
    – D.W.
    Jul 8 at 5:05

1 Answer 1


Given $L=(a+b)^*- a^nb^n-b^na^n$ which could be written as $L=(a+b)^*- (a^nb^n \cup b^na^n)=(a+b)^* \bigcap (a^nb^n \cup b^na^n)^\complement= (a+b)^* \bigcap \{(a+b)^*-(a^nb^n \cup b^na^n)\}=(a+b)^*\bigcap(\{a^mb^n | m\neq n\}\cup\{b^ma^n | m\neq n\}\cup a(a+b)^*a\cup b(a+b)^*b \cup (ab)^*b \cup (ba) ^*a) =\{a^mb^n | m\neq n\}\cup\{b^ma^n | m\neq n\}\cup a(a+b)^*a\cup b(a+b)^*b\cup (ab)^*b \cup (ba) ^*a,$

from here you could make $DPDA$ easily.

  • $\begingroup$ So abba not in the final language? Why not? $\endgroup$
    – cs_student
    Jul 9 at 22:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.