Prove that finding whether there are any states which will never be entered on any given...

Prove that finding whether there are any states which will never be entered on any given input is decidable in the case of a PDA, and, undecidable in case of a Turing machine.

Solutions

Expert Solution

Finding whether are any state in PDA which will never enter is a decidable problem because given the PDA with states and transition functions, there exist a deterministic algorithm to decide whether a particular state will be ever visited or not using following algorithm :-

1. Given the PDA with set of states Q and set of transitions functions , we can represent it as graph with set of states Q will be set of vertices and set of transitions of the form as the edge set.

2. Now to test whether any state q is every reachable in PDA, we have to check set of all possible path from state state to state q and what are the input requirement to reach at that state through a particular path.

3. Although there may be infinite number of path because of loops, still testing for reachability condition without going though loop will be sufficient to decide reachability of a particular state.

Since with finite numbers of trails, we can determine the reachability of state in PDA, hence this problem is decidable in PDA.

Same problem is undecidable in case of TM because if it were decidable that which state will be ever reachable and which state is not reachable, we could have solved halting problem which is one of the undecidable problem by performing below reduction.

Given the input <M,w> and we want to test whether M halts on w or not, we can create TM M₁ which on input x performs as follows:-

1. If x != w, then go to state q_reject and reject the input and halt.

2. If x = w, then M₁ will perform exactly a M on w.

Hence now if we are able to know whether M₁ ever reach to any of the halting state other than q_reject will help to determine whether M halts on w on not, because M₁ will go to any other state than q_reject only on input w and if M₁ go to some halting state on input x = w, this means M will also halt on w and hence we can decide whether <M,w> belongs to halting instance or not.

However since halting problem is undecidable and reducible to the problem of testing whether there is some state which is ever reachable or not in TM, hence this problem is also undecidable.

Please comment for any clarification.

venereology answered 7 months ago

Next > < Previous

Related Solutions

Problem 1: (a) Prove the statement: Two indifference curves can never intersect.(b) Verify whether the following...

Problem 1: (a) Prove the statement: Two indifference curves can never intersect.(b) Verify whether the following statement is true or false, and explain. A choice is rational when an indifference curve is tangent to the budget line. (c) I am indifferent between consuming bundle 1 (5 cookies and 10 chocolates) and bundle 2 (10 cookies and 5 chocolates). I am also indifferent between bundle 2 and bundle 3 (9 cookies and 15 chocolates). If I also stated that I prefer...

Please use any of the methods to prove whether each of the following arguments is valid...

Please use any of the methods to prove whether each of the following arguments is valid or invalid. For each problem, please identify the method that you have decided to employ and make sure to show your work. 1. It is obvious that nuclear energy is needed. Nuclear energy is needed if and only if solar energy cannot be harnessed. And it is also true both that solar energy can be harnessed only if funds to do so are available,...

Create a program that will calculate the factorial of any user entered integer. For any positive integer, the factorial is given as

Create a program that will calculate the factorial of any user entered integer. For any positive integer, the factorial is given as: n! = n·(n-1)·(n-2)·.……·3·2·1. The factorial of 0 is 1. If a number is negative, factorial does not exist and this program should display error message. Sample output dialogues should look like these: Enter an integer: -5 ERROR!!! Tactorial of a negative number doesn't exist Enter an integer: 10 Factorial = 3628800

the United States has entered into which of the following for the purpose of avoiding double...

the United States has entered into which of the following for the purpose of avoiding double taxation of income wuth respect to social security taxes. a. totalizatiom agreements b. social security agreements c. international agreements, d. double taxation avoidance agreements

Prove the following statements: (a) indifference curves can never intersect. (b) an indifference curve is never...

Prove the following statements: (a) indifference curves can never intersect. (b) an indifference curve is never positively-sloped.

prove that every integer is either even or odd but never both.

Prove whether the set of all proofs within any formal system is decidable, recognizable, or unrecognizable

Prove that any two groups with one element are isomorphic. Prove that any two groups with...

Prove that any two groups with one element are isomorphic. Prove that any two groups with two elements are isomorphic. Prove that any two groups with three elements are isomorphic.

Prove that the following statements are equivalent. A. The Euclidean parallel postulate holds. B. Given any...

Prove that the following statements are equivalent. A. The Euclidean parallel postulate holds. B. Given any triangle △ABC and given any segment DE, there exists a triangle △DEF having DE as one of its sides such that △ABC ∼ △DEF (Wallis’ postulate on the existance of similar triangles). (you cannot use measures)

Exercise 1.13.5: Determine and prove whether an argument in English is valid or invalid. Prove whether...

Exercise 1.13.5: Determine and prove whether an argument in English is valid or invalid. Prove whether each argument is valid or invalid. First find the form of the argument by defining predicates and expressing the hypotheses and the conclusion using the predicates. If the argument is valid, then use the rules of inference to prove that the form is valid. If the argument is invalid, give values for the predicates you defined for a small domain that demonstrate the argument...

Subjects