2
$\begingroup$

How would I go about using Cartesian construction to find the intersection between a PDA and a DFA?

Is there another term for Cartesian construction? Would it be similar to the procedure for finding the intersection/union of 2 DFAs?

$\endgroup$
6
$\begingroup$

The more common term is the "product construction".

The product of a PDA and a DFA is a PDA whose state space is the Cartesian product of the states of the two automata (just like in two DFAs), the transition function is similar to the product construction in DFAs, only the PDA component can act on the stack.

$\endgroup$

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.