qraymo Garden

Powered by 🌱Roam Garden

DEA

def/concept ein (D)EA besteht aus: sr

$A$ = ( $Q$ , $\Sigma$ , $\delta$ , $s$ , $F$ )

$Q$ , endliche Menge von Zuständen (Zustandsmenge)

$\Sigma$ , endliche Menge von Eingabesymbolen, Alphabet

$\delta$ : $Q \times \Sigma \rightarrow Q$ , eine Übergangsfunktion

$s$ $\in$ $Q$ , einem Startzustand

$F$ $\subseteq$ $Q$ , einer Menge von Endzuständen

def/description deterministisch, da sr

{{TODO}} $\delta$ - eine eindeutige Übergangsfunktion, d.h. es gibt keine Wahlmöglichkeiten

vgl. NEA, wo $\delta$ eine Übergangsrelation ist

Referenced in

EA

Zu jedem NEA gibt’s einen äquivalenten DEA.

reguläre Sprache

reguläre Sprache

regulär

reguläre Sprache $L$ $\iff$ regulärer Ausdruck α mit $L = L(\alpha)$ $\iff$ NEA $A$ , der $L(\alpha)$ erkennt $\iff$ DEA $\tilde{A}$ , der dieselbe Sprache wie $A$ erkennt

Vorlesung-02-Endliche-Automaten.pdf

Satz Jede reguläre Sprache $L$ wird von einem (deterministischen) endlichen Automaten (DEA) akzeptiert. * sr

February 19th, 2021

Jede reguläre Sprache $L$ wird von einem (deterministischen) endlichen Automaten (DEA) akzeptiert. {{7: wbCfktau_}} 📑 sr r/1

NEA

NEA $\rightsquigarrow$ DEA - durch Potenzmengenkonstruktion

EA

Potenzmengenkonstruktion: NEA -> DEA

EA

DEAs und formale Sprachen

reguläre Sprache