Entscheidbarkeit 78

Wortproblem

entscheidbar (CYK-Algorithmus)

Leerheitsproblem

entscheidbar

• Idee: markiere Variable $A$ mit $\left\{ x\in\Sigma^{*}\vert A\Rightarrow^{*}x\right\} \neq\emptyset$

Endlichkeitsproblem

entscheidbar

• $\left\vert L\right\vert=\infty\Leftrightarrow\exists x\in L:n\leq\left\vert x\right\vert<2n$

Gleichheit

Wenn $L_{1}$ det. kontextfrei, und $L_{2}$ regulär. Ist $L_{1}=L_{2}$ entscheidbar? Ja, siehe Buch.

Äquivalenzproblem

für DPDA's entscheidbar