1
$\begingroup$

Suppose, we have $L_1:=\{w\in\{a,b\}^*\mid \#_a(w) \equiv 0 \mod 4\}$ and $L_2:=\{w\in\{a,b\}^*\mid abaab \text{ is a substring of } w\}$. Now we want to create a Deterministic Push-Down Automaton for $L_1\cap L_2$

I've created PDA's for both languages:

$M'=(Q,\Sigma,\Gamma,\Delta,s,F)$ with $\Sigma=\{a,b\}$, $\Gamma=\{\}$, $Q=\{1,2,3,4\}$, $F=\{0\}$, $s=\{0\}$ and \begin{align} \Delta=\{&(0,a,\lambda,1,\lambda),(0,b,\lambda,0,\lambda)(1,a,\lambda,2,\lambda),(1,b,\lambda,1,\lambda),(2,a,\lambda,3,\lambda),(2,b,\lambda,2,\lambda)\\ &(3,a,\lambda,0,\lambda),(3,b,\lambda,3,\lambda)\} \end{align} where $\Delta\subseteq Q_{old}\times (\Sigma \cup \{\lambda\})\times(\Gamma\cup \lambda)\times Q_{new}\times\Gamma^*$

and

$M''=(Q,\Sigma,\Gamma,\Delta,s,F)$ with definitions above and $\Sigma=\{a,b\}$, $\Gamma=\{\}$, $Q=\{1,2,3,4,5,6\}$, $F=\{6\}$, $s=\{1\}$ and \begin{align} \Delta=\{&(1,a,\lambda,2,\lambda),(1,b,\lambda,1,\lambda),(2,a,\lambda,2,\lambda),(2,b,3,\lambda),(3,a,\lambda,4,\lambda),(3,b,\lambda,1,\lambda),\\&(4,a,\lambda,5,\lambda),(4,b,\lambda,3,\lambda),(5,a,\lambda,2,\lambda),(5,b,\lambda,6,\lambda),(6,a,\lambda,6,\lambda),(6,b,\lambda,6,\lambda)\} \end{align}

$M'$ accepts $L_1$ and $M''$ accepts $L_2$, but how to construct $M^{\star}=M'\cap M''$ which accepts $L_1\cap L_2$?

I know, that we could possibly do this with Deterministic Finite Automata, but I want to know how it would work with PDA's.

$\endgroup$

1 Answer 1

2
$\begingroup$

There is no general algorithm for computing a DPDA $M^*$ as the intersection of two DPDA $M,M'$; that problem is undecidable. See Undecidable problem intersection of two DCFL languages is DCFL? for a proof.

So, you will have to look for some pattern in this particular problem that makes it easier than the general case. Hint: what level in the Chomsky hierarchy is $L_1$ at? what about $L_2$?

$\endgroup$
5
  • $\begingroup$ They're both type 3 and we possibly don't need the stack of the PDA to compute them. Unfortunately I should use PDA's to do it... We heard something of the Union of 2 PDA's that only works with a PDA that needs the Stack and one PDA for a language of type 3 which doesn't need the stack so you can mix them up. One does things on the stack and the other one just works like a DFA... But I'm not sure how to really apply this all in this particular case. $\endgroup$
    – Doesbaddel
    Commented Dec 7, 2019 at 22:09
  • 1
    $\begingroup$ @Doesbaddel, great. So you know they are type 3. Could that be helpful? This is your exercise, so you'll need to take it from here. I suggest you spend some more time on it. $\endgroup$
    – D.W.
    Commented Dec 7, 2019 at 22:09
  • $\begingroup$ Yeah, I will try to do so. Can I use the algorithm for DFA's for intersection? Because both are of type 3 and then just change it to a PDA in the end? $\endgroup$
    – Doesbaddel
    Commented Dec 7, 2019 at 22:13
  • $\begingroup$ I've created DEA's for both languages. After that I created the DEA for the intersection and then minimized it. Out of that I created a push down automata that doesn't use the stack. $\endgroup$
    – Doesbaddel
    Commented Dec 10, 2019 at 9:29
  • 1
    $\begingroup$ @Doesbaddel, congratulations on solving the problem! Nice job. $\endgroup$
    – D.W.
    Commented Dec 10, 2019 at 9:36

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.