Nichtdeterministische Automaten

Question 1

Wofür steht NFA?

Answer 1

Nichtdeterministischer endelicher Automat

Question 2

Unterschied zwischen NFA und DFA?

Answer 2

• DFA = für jedes Symbol genau eine mögliche Transition
  + NFA =
  -> mehrere gleiche Transitionen erlaubt
  -> nicht beschriftete Transition ist erlaubt
  -> nicht alle Symbole müssen als ausgehend Transitionen vorhanden sein

Question 3

Was besagt das Kleene’s Theorem?

Answer 3

Reguläre Ausdrücke, DFAs und NFAs sind äquivalente Modelle, in dem Sinn, dass sie alle reguläre Sprachen charakterisieren.

Question 4

Wann ist eine Sprache regulär?

Answer 4

Sprache ist regulär, wenn es regulären Ausdruck gibt, der sie beschreibt

Question 5

Sind NFAs und DFAs äquivalent?

Answer 5

Jeder DFA ist auch ein NFA

Question 6

Wieviele zustände hat ein DFA, wenn ein NFA n Zustände hat?

Answer 6

Wenn NFA n Zustände hat, hat DFA maximal 2 hoch n Zustände

Question 7

Wie ist ein NFA aufgebaut?

Answer 7

Q: Zustandsmenge
E: Eingabealphabet, edlich
d: Zustandsübergangsfunktion
q0: Startzustand (mehrere Startpunkte)
F: Finalmenge (mehrere Endpunkte)

Question 8

Wie löst man das Wortproblem in einem NFA?

Answer 8

Suche mindestens eine Sequenz von Zustandstransitionen

Question 9

Gibt es einen regulären Ausdruck, der die gleiche Anzahl a’s und b’s erkennt?

Answer 9

Nein kann nicht erreicht werden.

Question 10

Sprache der korrekten Klammerausdrücke Java Klammerung?

Answer 10

Nein es existiert kein regulärer Ausdruck

Question 11

Wann gilt ein Eingangswort als akzeptiert?

Answer 11

Wenn es eine Sequenz gibt, die vom Startpunkt 0 in den Akzeptanzstand bringt.

Question 12

Was passiert, wenn ein Pfeil mit keinem Symbol beschriftet ist?

Answer 12

Es kann ein Zustandswechsel stattfinden muss aber nicht. Leeres Wort (Epsilon)