
Theory of Computation Theoretical Computer Science  Automata Theory, Computability Theory, and Computational Complexity Theory 
 LinkBack  Thread Tools  Display Modes 
June 25th, 2008, 03:22 AM  #1 
Joined: Jun 2008 Posts: 2  theory of computation sipser problems
Hi all, I am doin masters and studying Theroy of Computation.I have my final paper after few days and i am 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(R) 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. www.farazch.byethost13.com 
My Computer Forum is free to register and we welcome everyone! 
June 25th, 2008, 08:00 AM  #2 
Joined: Dec 2007 Posts: 138  Re: theory of computation sipser problems
Unfortunately, you've probably got a lot more computation theory than any of us here... We're mostly semiamateur mathematicians, who happen to have an interest in computer science. I will someday be able to answer these questions (I hope), but not any time soon. Sorry 
June 25th, 2008, 09:31 AM  #3 
Joined: Dec 2007 Posts: 232  Re: theory of computation sipser problems
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. I think a greedy search would work here. 4) Let T = {<M>M is a TM that accepts w reverse whenever i accepts w}.Show that T is undecidable. What is i? In any case it's not hard to see that on a standard (twosided unbounded) tape it's no harder to accept a string than its reverse (just reverse the Turing machine), so if i is undecidable then so is T. 
June 25th, 2008, 09:52 AM  #4 
Joined: Jun 2008 Posts: 2  Re: theory of computation sipser problems
sorry i made a typing error,question is 4) Let T = {<M>M is a TM that accepts w reverse whenever it accepts w}.Show that T is undecidable. yes wat u said tht does make sense bt can u elobarate a bit more.Sumthin like formal proof to show undecidability. 
March 6th, 2009, 02:05 AM  #5 
Joined: Mar 2009 Posts: 1  Re: theory of computation sipser problems
contact me on softdew225@yahoo.com i will send you the manual for it.

April 27th, 2009, 01:21 AM  #6 
Joined: Apr 2009 Posts: 2  help!
well then, as u can see I´m a new member here... hello everybody ! I´m actually studing computer science this is my first year... the course it´s bloody practical so exhaustive math is out of its scope though I luv math ´n I´ve trying to solve some problems my own... one of the exercices I´ve trying to solve it´s all about tautologies and it says: Using truth tables or otherwise, check that each of the following is a tautology: (I´ll use C# notation to write down the logical sentences ) a) p>(p  q) b) ((p && !q)>q)>(p>q) c) p>(q>p) d) (p  (p && q))<>p e) (p>q)<>(!q> !p) by supposing, p=True q=True p=True q=False p=False q=True p=False q=False in all the cases I´ve obtained that, all of them are tautologies though I huv some doubts about my results... :? I´d feel glad if someone could check this up, to see whether I´ve made a mistake or not... thankies!!! 
June 24th, 2009, 10:19 PM  #7 
Joined: Jun 2009 Posts: 21  Re: theory of computation sipser problems
I just came across this post and get it very informative as i seeking here. Thanks for sharing it.

March 2nd, 2011, 01:28 PM  #8 
Joined: Mar 2011 Posts: 1  Re: theory of computation sipser problems
Dear tocmca : sir can u plz mail these solutions of martin via sending me a mail.. i cant access the group so.. mail me at dtech112@hotmail.com .. i shall be very thank full to u 
April 21st, 2012, 09:08 PM  #9 
Joined: Apr 2012 Posts: 1  Re: theory of computation sipser problems
Hi to all, I got answer key for John C. Martin Book and very good reading material (handwritten) from http://theoryofcomputations.blogspot.com Get it...Enjoy Studying toc.mca 

Tags 
computation, problems, sipser, theory 
Search tags for this page 
Click on a term to search for related topics.

Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Theory of Computation  Amina  Theory of Computation  0  October 27th, 2013 06:12 AM 
Micheal Sipser  Theory of Computation 2nd ed. Solutions  AlienX  Theory of Computation  0  September 26th, 2011 12:33 AM 
Problems with my pc, help  checkitout  Tech Support  6  May 12th, 2010 08:36 AM 
GA in numerical computation of ODE  hasan  Artificial Intelligence  0  July 16th, 2009 01:53 PM 
Problems with my pc, help  checkitout  Databases  0  December 31st, 1969 04:00 PM 