Theory of computation help

[farazch]

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