Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$?
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.
