My Computer Forum Computer Science Forum

Go Back   My Computer Forum > Computer Science Forum > Theory of Computation

Theory of Computation Theoretical Computer Science - Automata Theory, Computability Theory, and Computational Complexity Theory


Reply
 
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
farazch is offline  
 

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 semi-amateur 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
cknapp is offline  
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 (two-sided 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.
CRGreathouse is offline  
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.
farazch is offline  
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.
masood is offline  
April 27th, 2009, 01:21 AM   #6
 
Joined: Apr 2009
Posts: 2
help!

well then, as u can see Im a new member here... hello everybody !
Im actually studing computer science this is my first year... the course its bloody practical so exhaustive math is out of its scope though I luv math n Ive trying to solve some problems my own...
one of the exercices Ive trying to solve its all about tautologies and it says:

Using truth tables or otherwise, check that each of the following is a tautology:

(Ill 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 Ive obtained that, all of them are tautologies though I huv some doubts about my results... :?
Id feel glad if someone could check this up, to see whether Ive made a mistake or not... thankies!!!
ro_ddrie is offline  
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.
daveD is offline  
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 d-tech112@hotmail.com .. i shall be very thank full to u
wassay7 is offline  
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
toc.mca is offline  
Reply

  My Computer Forum > Computer Science Forum > Theory of Computation

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





Copyright © 2018 My Computer Forum Forum. All rights reserved.