# DPDA for language $L=\{a,b\}^* \setminus a^nb^n \setminus b^na^n$

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.

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

• 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).
– D.W.
Jul 7 at 21:14
• @D.W. Corrected, you can remove your downvote. Jul 7 at 21:48
• @cs_student how is it corrected? "/" mean? Jul 7 at 21:58
• @AlokMaity look closely. Second sentence and explanation after it. Jul 7 at 22:01
• 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.
– D.W.
Jul 8 at 5:05

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.