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

| cite | improve this answer | |
$\endgroup$
  • $\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 Dec 7 '19 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. Dec 7 '19 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 Dec 7 '19 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 Dec 10 '19 at 9:29
  • 1
    $\begingroup$ @Doesbaddel, congratulations on solving the problem! Nice job. $\endgroup$ – D.W. Dec 10 '19 at 9:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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