1
$\begingroup$

Show that it is unsolvable whether a given context-sensitive language is context fre.

And, show that the emptiness problem is solvable for one-way nondeterministic stack automata.

I don't know how to use PCP for first one. And also, i have no idea for solution of secund one.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.