2
$\begingroup$

Given the PDA $P = (Q_P,\Sigma,\Gamma_P,\delta_P,F_P)$ and the DFA $D = (Q_D, \Sigma, \delta_D,q_D,F_D)$

What is the 6-tuple definition of the PDA such that: $L(P') = L(P) \cap L(D)$

I don't understand what the intersection of these two FAs represent, and my only guess at what the 6-tuple is would be something along the lines of: $P'=(Q,\Sigma,\Gamma,\delta,q_0,F)$ such that:

$P=Q_P$ x $Q_D$
$\Sigma = \Sigma$
$\Gamma =..?$
$\delta =..?$
$F =..?$

The only other resource on this site I found that is remotely similar to this question is:
Cartesian construction of PDA and DFA

However, I didn't find the answer to be sufficient.

$\endgroup$
1
  • 2
    $\begingroup$ Hint: look at the intersection construction for two DFA. Then lift it to this setting. $\endgroup$
    – Raphael
    Nov 5 '15 at 7:04
3
$\begingroup$

The idea of the intersection is to construct a PDA that keeps track of the original PDA's state in the first component of the state (in the $Q_P$ component) together with the stack, and keep track of the DFA's state in the $Q_D$ component. If both accept by final state, you just need to accept if both automata end up in a final state.

$\endgroup$
0
2
$\begingroup$

The formal description of the new machine is a bit involved, but the basic idea is simple: for every new input character, do the original PDA's move and the DFA's move in parallel (i.e., work in the context of the Cartesian product of the two machines). If they both lead to an accept state, the new machine should accept; if one or the other doesn't accept, then the new machine won't. I'll leave the details to you.

$\endgroup$
0

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.