finite-state machine

finite-state machine (tsz. finite-state machines)

1. (informatika, mesterséges intelligencia) véges állapotú gép

A véges állapotú automata egy olyan absztrakt számítási modell, amely egy bemeneti szimbólumsorozatot dolgoz fel állapotok között váltogatva, az adott átmeneti szabályok szerint. Az FSM csak egy adott pillanatban aktív állapotban van, és véges számú állapottal rendelkezik.

Egy determinisztikus véges állapotú automata (DFA) 5 komponensből áll:

$${\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)}$$

Szimbólum	Jelentés
${\textstyle Q}$	Az állapotok véges halmaza
${\textstyle \Sigma }$	Bemeneti ábécé (szimbólumok halmaza)
${\textstyle \delta }$	Átmenetfüggvény: ${\textstyle \delta (q,a)=q'}$
${\textstyle q_{0}\in Q}$	Kezdőállapot
${\textstyle F\subseteq Q}$	Elfogadó (vég)állapotok halmaza

• Minden állapotból minden bemenetre pontosan egy átmenet van.
• Nincs bizonytalanság.
• Könnyen implementálható.

• Egy állapotból egy bemenetre több lehetséges átmenet is lehet.
• Tartalmazhat ε-átmeneteket (üres bemenet nélküli ugrás).
• Minden NFA-nak van egy DFA megfelelője.

1. Az automata a kezdőállapotban van: ${\textstyle q_{0}}$
2. Beolvassa az első szimbólumot a bemeneti szóból
3. Az aktuális állapot és szimbólum alapján új állapotba lép
4. Ha a szó véget ér, és az automata elfogadó állapotban van, akkor a szó elfogadott

Ismerje fel azokat a bináris szavakat (${\textstyle \Sigma =\{0,1\}}$), amelyek páros számú 1-est tartalmaznak.

• Állapotok:
  • ${\textstyle q_{0}}$: páros számú 1 (kezdeti és elfogadó)
  • ${\textstyle q_{1}}$: páratlan számú 1
• Átmenetfüggvény ${\textstyle \delta }$:
  • ${\textstyle \delta (q_{0},0)=q_{0}}$
  • ${\textstyle \delta (q_{0},1)=q_{1}}$
  • ${\textstyle \delta (q_{1},0)=q_{1}}$
  • ${\textstyle \delta (q_{1},1)=q_{0}}$

Mert:

• Véges számú állapot van
• Az automata nem tud memóriát tárolni a korábbi bemenetekről (csak az aktuális állapot számít)

def fsm(word):
    state = 'q0'
    for symbol in word:
        if state == 'q0':
            state = 'q1' if symbol == '1' else 'q0'
        elif state == 'q1':
            state = 'q0' if symbol == '1' else 'q1'
    return state == 'q0'  # csak itt fogad el

print(fsm("1011"))  # True, mert 2 db 1 van → páros
print(fsm("111"))   # False, mert 3 db 1 → páratlan

• Minden reguláris nyelvhez van véges automata, ami felismeri.
• Ez a formális nyelvészet és számításelmélet alapja.
• Kapcsolódik a reguláris kifejezésekhez: pl. (ab)*

• finite-state machine - Szótár.net (en-hu)
• finite-state machine - Sztaki (en-hu)
• finite-state machine - Merriam–Webster
• finite-state machine - Cambridge
• finite-state machine - WordNet
• finite-state machine - Яндекс (en-ru)
• finite-state machine - Google (en-hu)
• finite-state machine - Wikidata
• finite-state machine - Wikipédia (angol)