Végállapotok

Végállapotok (más néven elfogadó vagy akceptáló állapotok) a formális nyelvek és véges automata-elmélet központi fogalmai. Egy véges automata állapotainak halmaza közül azok tartoznak a végállapotokhoz, amelyekbe érkezve a feldolgozott bemeneti szó végén az automata elfogadja a szót. A kezdő állapotot q0-nak jelöljük, a végállapotok halmazát F-vel. Egy szó w esetén az A automata esetén a w elfogadott, ha δ*(q0, w) ∈ F, ahol δ* a zárt kifejezés a gép teljes átviteli függvényére értelmezett hurok nélküli lépések után felépített eljárást jelöli. Ha q0 ∈ F, akkor az ε (üres bemenet) is elfogadható szó.

Különbségek a típusok között: determinisztikus véges automata (DFA) esetében minden állapotból egyetlen továbbhaladási út van adott bemeneti jelre, így minden szó pontosan egy útvonalon végződik, és vagy elfogadó, vagy nem elfogadó állapotban ér véget. nondeterminista véges automata (NFA) esetében több út is létezhet, és egy szó akkor elfogadható, ha van olyan út, amely végződik egy végállapotban. Bármely NFA találhatóhoz átalakítható egy ekvivalens DFA, így ugyanazon nyelvet lehet leírni mindkét modellben.

Jelentőség: végállapotok nélkül nem lehet meghatározni, hogy egy szó elfogadott-e; így a végállapotok meghatározása alapvető a szabályos nyelvek reprezentációjában, a lexikai elemzésben és a formális nyelvtanok meghatározásában. Megjegyzés: a kifejezés más területeken esetleg abszorbing vagy végfokozati állapotokat is jelenthet, de ezen a területen főként az elfogadó állapotokra utalunk.

---