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.


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.