Another Mystery Algorithm
Consider the following mystery algorithm:
Input:
PDA $M = (Q,\Sigma,\Gamma,s,\Delta,W)$ and
NDFA $M' = (Q',\Sigma,\Delta',s',W')$, where $M'$
has no λ-transitions
Output:
PDA $M^* = (Q \times Q',\Sigma,\Gamma,(s,s'),\Delta^*,W \times W')$,
where
$$
\Delta^* = \left\{((p,p'),x,y,(q,q'),z)\ \big|\
(p,x,y,q,z) \in\Delta
\wedge (p',x,q') \in \Delta'\right\}
\cup
\left\{
((p,p'),\lambda,y,(q,p'),z)\ \big| (p,\lambda,y,q,z) \in
\Delta
\right\}
$$
- What output does the algorithm produce given the
following as input:
-
Is the requirement that input $M'$ has no
$\lambda$-transitions a serious limitation?
-
What general property of context-free languages and
regular languages does this algorithm prove?