logo

TechCodeview

Automatisch fertig

  • Zur Mustererkennung werden endliche Automaten verwendet.
  • Es nimmt die Symbolzeichenfolge als Eingabe und ändert seinen Status entsprechend. Wenn das gewünschte Symbol gefunden wird, erfolgt der Übergang.
  • Beim Übergang können die Automaten entweder in den nächsten Zustand wechseln oder im gleichen Zustand bleiben.
  • Endliche Automaten haben zwei Zustände, Status akzeptieren oder Status ablehnen . Wenn die Eingabezeichenfolge erfolgreich verarbeitet wurde und der Automat seinen Endzustand erreicht hat, wird er akzeptiert.

Formale Definition von FA

Ein endlicher Automat ist eine Sammlung von 5-Tupeln (Q, ∑, δ, q0, F), wobei:

 Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function

Modell endlicher Automaten:

Endliche Automaten können durch Eingabeband und endliche Kontrolle dargestellt werden.

Eingabeband: Es handelt sich um ein lineares Band mit einer bestimmten Anzahl von Zellen. Jedes Eingabesymbol wird in jeder Zelle platziert.

Endliche Kontrolle: Die endliche Kontrolle entscheidet über den nächsten Zustand beim Empfang einer bestimmten Eingabe vom Eingabeband. Der Bandleser liest die Zellen einzeln von links nach rechts, und es wird immer nur ein Eingabesymbol gelesen.

Automatisch fertig

Arten von Automaten:

Es gibt zwei Arten endlicher Automaten:

  1. DFA (deterministische endliche Automaten)
  2. NFA (nicht deterministische endliche Automaten)
Automatisch fertig

1. DFA

DFA bezieht sich auf deterministische endliche Automaten. Deterministisch bezieht sich auf die Einzigartigkeit der Berechnung. Beim DFA wechselt die Maschine nur für ein bestimmtes Eingabezeichen in einen Zustand. DFA akzeptiert die Nullverschiebung nicht.

2. NFA

NFA steht für nichtdeterministische endliche Automaten. Es dient dazu, beliebig viele Zustände für einen bestimmten Eingang zu übertragen. Es kann die Nullbewegung akzeptieren.

Einige wichtige Punkte zu DFA und NFA:

  1. Jeder DFA ist NFA, aber NFA ist nicht DFA.
  2. Sowohl in NFA als auch in DFA kann es mehrere Endzustände geben.
  3. DFA wird in der lexikalischen Analyse im Compiler verwendet.
  4. NFA ist eher ein theoretisches Konzept.