计算机理论引导之可判定性-可判定语言

Computability Theory - Decidability - Decidable Languages

注意：这篇文章需要读者有《计算机理论引导》的相关背景知识。本文可能包含错误，如果您发现相关问题，欢迎通过本站的关于页面的电子邮箱与我联系。

Intro

We know Church-Turing thesis essentially says that the notion of algorithm are equivalent to Turing machine(TM). A TM can simulate a computer by simulating the basic operations like addition, multiplication, division, etc. A computer can also simulate a TM to keep track of tape contents by using programming languages like Python.

If a TM cannot solve a problem, that means a computer can also not solve that problem. When we say "cannot solve a problem" in previous sentence. The words solve means there is no decider for a given Language $L$.

Here, no decider doesn't means no recognizer.

Can Turing machine answer questions about what other machines(DFAs, for example) can do/be solved?

• We can build up to Turing machines which allows us to show that a problem can be solved.

That's what what this article will show next.

Decidable Languages

Representation / Encoding

A string representation/encoding of machine $M$ can be written as $\langle M \rangle$.

Acceptance problem for DFA

The acceptance problem for DFAs of testing whether a particular DFA accepts a given string can be expressed as a language, $A_{DFA}$.

$$ A_{DFA} = \{ \langle B,w \rangle \mid B \text{ is a DFA that accepts input string } w\} $$

• $A$ states for an acceptance problem.
• $\langle B,w \rangle$ means whether some string encoding of a DFA $B$ accepts an input $w$.

Overall, it means the problem of testing whether a DFA $B$ accepts an input $w$ is the same as the problem of testing whether $\langle B,w \rangle \in A_{DFA}$.

Theorem:

$A_{DFA}$ is decidable. (In another words, a TM exists for $A_{DFA}$ that always halts)

Proof:

$M$ = "On input $\langle B,w \rangle$, where $B$ is a DFA and $w$ is a string:

1. Simulate $B$ on input $w$.
2. If the simulation($B$) ends in an accept state, $M$ accepts. If it ends in a non-accept state, $M$ reject."

Note: $M$ is a Turing machine, and $M$ is a decider for $A_{DFA}$. It's important to understand only a language can be decidable, a machine is a decider.

Acceptance problem for NFA

$$ A_{NFA} = \{ \langle B,w \rangle \mid B \text{ is a NFA that accepts input string } w\} $$

Theorem:

$A_{NFA}$ is decidable.

Proof:

$N$ = "On input $\langle B, w \rangle$, where $B$ is a NFA and $w$ is a string:

1. Convert NFA $B$ to an equivalent DFA $C$.
2. Run the Turing machine $M$ for $A_{DFA}$ on $\langle C, w \rangle$
3. If $M$ accepts, accept; otherwise, reject." (Output whatever the Turing machine $M$ says)

Note 01: In step #2, it is important to know when we send something to machine $M$. Let's for example $\langle X, x \rangle$, $X$ has to be a DFA(NOT an NFA or something else). It is because we defined that in problem "Acceptance problem for DFA".

Note 02: The reason why we need convert a DFA to a NFA is because a NFA may includes $\epsilon$ transition. So, it may ends up with a loop and run forever.

Acceptance problem for REX

$$ A_{REX} = \{ \langle R,w \rangle \mid R \text{ is a regular expression that generates string } w\} $$

Theorem:

$A_{REX}$ is decidable.

Proof:

$P$ = "On input $\langle R, w \rangle$, where $R$ is a regular expression and $w$ is a string:

1. Convert regular expression $R$ to an equivalent NFA $A$.
2. Run TM $N$ on input $\langle A, w \rangle$
3. If $N$ accepts, accept; if $N$ rejects, reject."

Emptiness problem for DFA

$$ E_{DFA} = \{ \langle A \rangle \mid A \text{ is a DFA and } L(A) = \empty\} $$

• $E$ states for an emptiness problem.

Overall, it means whether a DFA $A$ accepts nothing(no accepting string in language $A$).

Theorem:

$E_{DFA}$ is decidable.

Proof:

$T$ = "On input $\langle A \rangle$, where $A$ is a DFA:

1. Mark the start state of $A$.

2. Repeat until no new states get marked:

   1. Mark any state that has a transition coming into it from any state that is already marked.
3. If no accept state is marked, accept; otherwise, reject."

Note: A naive way to think about this problem is by looking at, if DFA $A$ has a final states. That is NOT true. A DFA can have a unreachable final states, which has a final states but accepting nothing.

A right way to think of the problem is that if there exists a set of transitions allow us to reach final state.

Equality problem for DFA

$$ EQ_{DFA} = \{ \langle A,B \rangle \mid A \text{ and } B \text{ are DFAs and } L(A) = L(B)\} $$

Theorem:

$EQ_{DFA}$ is decidable.

Proof:

$$ L(C) = (L(A)\cap \overline{L(B)}) \cup (\overline{L(A)} \cap L(B)) $$

$F$ = "On input $\langle A,B \rangle$, where $A$ and $B$ are DFAs:

1. Construct DFA $C$ as described.
2. Run TM $T$ on input $\langle C \rangle$.
3. If $T$ accepts, accept. If $T$ rejects, reject."

It's important to understand the idea behind the proof algorithm:

$$ \langle A,B \rangle \in EQ_{DFA} \iff L(A) = L(B) \\ \iff L(A) \subseteq L(B) \text{ AND } L(B) \subseteq L(A) $$

We also know:

$$ L(A) \subseteq L(B) \iff L(A) \cap \overline{L(B)} = \empty \\ L(B) \subseteq L(A) \iff L(B) \cap \overline{L(A)} = \empty $$

That's how we got $L(C)$:

$$ L(C) = (L(A)\cap \overline{L(B)}) \cup (\overline{L(A)} \cap L(B)) $$

Acceptance problem for CFG

$$ A_{CFG} = \{ \langle G,w \rangle \mid G \text{ is a CFG that accepts input string } w\} $$

Theorem:

$A_{CFG}$ is decidable.

This implies $A_{PDA}$ is also decidable, since we can convert a CFG into a PDA.

Proof:

$S$ = "On input $\langle G,w \rangle$, where $G$ is a CFG and $w$ is a string:

1. Convert $G$ to an equivalent grammer $C$ in Chomsky normal form(CNF).
2. If $w=\epsilon$, and $S \to \epsilon$ is a rule in $C$, accept; If $S \to \epsilon$ is a not rule in $C$, reject.
3. let $n$ be the length of string $w$.
4. Generate all possible derivations of $2n-1$.
5. If any of the dervations result in $w$, accept; otherwise, reject"

Acceptance problem for CFL

$$ A_{CFL} = \{ \langle G,w \rangle \mid G \text{ is a CFL that accepts input string } w\} $$

Theorem:

$A_{CFL}$ is decidable.

Proof:

$M_G$ = "On input $w$:

1. Run TM $S$ on input $ \langle G,w \rangle$.
2. If this machine accepts, accept; if it rejects, reject"

Emptiness problem for CFG

$$ E_{CFG} = \{ \langle G \rangle \mid G \text{ is a CFG and } L(G) = \empty\} $$

Theorem:

$E_{CFG}$ is decidable.

Proof:

$R$ = "On input $\langle G \rangle$, where $G$ is a CFG:

1. Mark all terminal symbols in $G$.

2. Repeat until no new variables get marked:

   1. Mark any variable $A$ where $G$ has a rule $A \to U_1 U_2 ... U_k$ and each symbol $U_1, ..., U_k$ has already marked.
3. If the start variable is not marked, accept; otherwise, reject."

Chomsky Hierarchy

Summary