Problem Detail: 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.
$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.
Asked By : milkywayz
Answered By : vonbrand
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/49091
