Jedes Problem, das durch einen endlichen Automaten gelöst wird, ist in P.

8

Nach meiner heutigen Theorie der Berechnungstheorie kam mir die Frage in den Sinn: Wenn ein Problem mit einem endlichen Automaten gelöst werden kann, gehört dieses Problem zu P.

Ich denke, es ist wahr, da Automaten sehr einfache Sprachen erkennen, würden alle diese Sprachen Polynomalgorithmen haben, um sie zu lösen. Stimmt es also, dass jedes Problem, das durch einen endlichen Automaten gelöst wird, in P ist?

complexity-theory automata finite-automata polynomial-time Sisyphus
quelle

15

REG \subseteq P.,

$\text{REG} \subseteq \text{P},$

REG

$\text{REG}$

\begin{matrix} (*) & REG \subseteq DTIME (n), \end{matrix}

$\text{REG} \subseteq \text{DTIME}(n), \tag{*}$

DTIME (n)

$\text{DTIME}(n)$

P

$\text{P}$

$\text{REG}$ $n$

REG = DSPACE (0) = DSPACE (k)

$\text{REG} = \text{DSPACE}(0) = \text{DSPACE}(k)$

k

$k$

6005
quelle

7

Ja, das stimmt. Für jedes dieser Probleme gibt es einen DFA, der die Sprache entscheidet, und die Überprüfung, ob ein Wort von einem DFA akzeptiert wird, kann leicht zeitlich linear in der Länge des Wortes durchgeführt werden.

Pontus
quelle

Jedes Problem, das durch einen endlichen Automaten gelöst wird, ist in P.

Antworten: