2
You're almost there. Yes, the intersection of two context-free languages is in general not context-free, but you have more structure here: one of your languages is regular! The intersection of a regular language and a context-free language is context-free, which gives us something to work with.
So. We have some DFA $M$, and we can build a PDA $N$ which ...
1
Given that, I would expect that for any reasonable model of computation, if $f : A \rightarrow B$ and $g : B \rightarrow C$ are computable, then $g \circ f : A \rightarrow C$ should be as well.
Let's say our model is quadratic time computation. If $f$ is the function which maps a string of length $n$ to a string of $n^2$ zeroes, then $f$ is computable in ...
Only top voted, non community-wiki answers of a minimum length are eligible
