0
$\begingroup$

In a practice midterm question, there's the following question. I am confused about why can't we just return the negation of the output of the FSA, instead of converting it into a Turing Machine.

(d) Explain how to construct an algorithm that solves the following problem. If such an algorithm does not exist, state that it does not exist and prove your claim.

Input: Finite state automaton that accepts a language S, and a string w;

Question: Does S reject w?

Answer: Employ the algorithm of Kleene’s Theorem to convert the argument automaton into a deterministic finite automaton, then convert the latter (deterministic) automaton into a deterministic Turing Machine that decides S. Finally, run this Turing machine on w and return the negation of its decision.

$\endgroup$
2
  • $\begingroup$ DFAs can only recognize regular languages. Turing Machines can pretty much handle anything. The difference is memory—Turing Machines have infinite tape whereas DFAs have finite memory. $\endgroup$ Commented May 7 at 1:43
  • $\begingroup$ Your intuition is correct: you just have to run the deterministic automaton on the input and negate the result. $\endgroup$ Commented May 7 at 2:08

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.