Sprache

[[kontextfreie Sprache]]

reguläre Sprachen und [[kontextfreie Sprache]]n

forward:: [[kontextfreie Sprache]]

Sprachen, Probleme, Zeitkomplexität

Zu jedem NEA $A$ mit $\epsilon$-Übergänge gibts einen NEA $\tilde{A}$ ohne $\epsilon$-Übergänge, der dieselbe Sprache akzeptiert* und nicht mehr Zustände hat da nur Übergänge hinzukommen

$\iff$ akzeptieren dieselbe Sprache