-2
$\begingroup$

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$?

$\endgroup$
6
  • $\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, 2023 at 21:14
  • $\begingroup$ @D.W. Corrected, you can remove your downvote. $\endgroup$
    – cs_student
    Jul 7, 2023 at 21:48
  • $\begingroup$ @cs_student how is it corrected? "/" mean? $\endgroup$
    – S. M.
    Jul 7, 2023 at 21:58
  • $\begingroup$ @AlokMaity look closely. Second sentence and explanation after it. $\endgroup$
    – cs_student
    Jul 7, 2023 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, 2023 at 5:05

1 Answer 1

1
$\begingroup$

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.

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

Your Answer

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

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