farazch Posted June 21, 2008 Posted June 21, 2008 Hi all, I am doin masters and studying Theroy of Computation.I have my final paper after few days and i m facing some serious problem regarding exercises of Theroy of Computation book "Sipser - Introduction to the theory of computation - 2nd EId".I tried to search the sol on internet but didnt find it anywhere.Plz help me if anyone can provide me with the sol or with the link where i can get help regarding exercise quiestions.Some of the exercise questions are solved while some are not.I am writing few of the questions which r troubling me.Please if anyone can give me the sol of these. 1) Let INFINITE PDA = {<M>,M is a PDA and L(M) is an infinite language}.Show that INFINITE PDA is decidable. 2)Let A = {<R,S>R and S are regular expressions and L® is subset of L(S)}.Show that A is decidable. 3)Let A = {<R>|R is a regular expression describing a language containing atleast one string w that has 111 as a substring(I.e,w=x111y for some x and y).Show that A is decidable. 4) Let T = {<M>|M is a TM that accepts w reverse whenever i accepts w}.Show that T is undecidable. These are few of the questions.Once i get the answers of these i will get the idea and will be able to solve other problems.So please any help will do lot for me. Thanks. http://www.farazch.byethost13.com
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now