New answers tagged

0

Above answers are excellently written. But one other approach would be helpful I think. We want to prove that if $L(A)$ is a $CFL$ and $L(B)$ is a regular then $L(A/B) = \{w\space|\space wx \in A,\space x\in B,\space w\in \Sigma^*\, ,\space x\in \Sigma^*\}$ is also a $CFL$. Let's use fact that set of regular languages and set of context free languages are ...


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 ...


Top 50 recent answers are included