Math Is Fun Forum

farazch

Member

Registered: 2008-06-21

Posts: 3

Theory of computation help

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.

Questions removed - Ricky

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

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Theory of computation help

I'm sorry farazch, but that would be cheating.  We are here to help, we can't do a take home final for you.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

farazch

Member

Registered: 2008-06-21

Posts: 3

Re: Theory of computation help

i think u didnt understand the situation.These r the questions frm book exercise and most of the questions are answered there.I tried to solve others and i done those bt these r the questions in which i am facing problem.I put my effort to solve them bt unseccessful so i feel this the place which could help me.If i didnt get any help from here ,those concepts will remain unclear.These questions are not an assignment questions.so it doesnt come into cheating i feel.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: Theory of computation help

Ah, I see.  What confused me was:

I have my final paper after few days and i
am facing some serious problem regarding exercises of Theroy of Computation book

Which made it sound like the exercises were part of the paper.  You may post them again, as I unfortunately have no way to undo my edit.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

farazch

Member

Registered: 2008-06-21

Posts: 3

Re: Theory of computation help

Alright let me list my problems agin :

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.

Hoping to get some answers rite as only 3 days left for my exam