automata theory

automata theory (tsz. automata theories)

1. (informatika, mesterséges intelligencia) automaták elmélete

Az automaták elmélete olyan matematikai modellekkel foglalkozik, amelyek formálisan írják le, hogyan dolgozzák fel a gépek (automaták) a szimbólumokból álló bemeneti sorozatokat. Ezek a modellek alapját képezik:

• fordítók tervezésének (pl. programozási nyelvek elemzése)
• szövegfeldolgozásnak
• nyelvelméletnek
• mesterséges intelligencia egyes területeinek

• Véges szimbólumhalmaz, jele: ${\textstyle \Sigma }$ Pl.: ${\textstyle \Sigma =\{a,b\}}$

• Szimbólumok véges sorozata az ábécéből Pl.: „abba” egy szó a ${\textstyle \{a,b\}}$ ábécén

• Szavak egy halmaza, amit egy automata felismerhet Pl.: az összes olyan szó, ami „a”-val kezdődik és „b”-vel végződik

• Ezek reguláris nyelveket ismernek fel
• Állapotdiagrammal ábrázolhatók

📌 Példa: ismerje fel azokat a szavakat, amelyek pontosan egy a betűt tartalmaznak

• Van egy veremtárolója (stack) is
• Képes kontekstszenzitív struktúrákat kezelni (pl. zárójelezés)
• Formális nyelvek: determinisztikus és nem-determinisztikus PDA-k
• Képes leírni a programozási nyelvek szintaxisát

📌 Példa: ismerje fel az összes olyan szót, ahol az a-k száma megegyezik a b-k számával

• A legerősebb modell
• Tartalmaz egy végtelen hosszú szalagot és fejjel olvas/ír
• Képes bármely algoritmikus probléma szimulálására
• Ez a “számításelmélet” alapja

📌 Példa: összeadás vagy szorzás végrehajtása szalagon

Egy determinisztikus véges automata 5 elemből áll:

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

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

Ismerje fel azokat a szavakat a ${\textstyle \{0,1\}}$ ábécén, amik páros számú 1-est tartalmaznak:

Állapotok:

• ${\textstyle q_{0}}$: páros számú 1 eddig
• ${\textstyle q_{1}}$: páratlan számú 1 eddig

Átmenetek:

• 0 → nem változtat állapotot
• 1 → váltogatja az állapotokat

Elfogadó állapot: ${\textstyle q_{0}}$

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