Automaták

VDA - (véges determinisztukus automata)

• \(A=(Q,T,\delta,q_0,F)\)
  • \(Q\)
    • Az állapotok nem üres halamza
  • \(T\)
    • Input szimbólumok ábécéje
  • \(\delta:\;Q\times T\to Q\)
    • Állapot-átmeneti függvény
  • \(q_0\in Q\)
    • Kezdőállapot
  • \(F\subseteq Q\)
    • Elfogadóűllapotok halmaza

Állapot átmenet

Alternatív jelölés

\(\delta(q,a)=p\)

\(qa\top\)

Közvetlen redukció

• \(A=(Q,T,\delta,q_0,F)\)
  • \(u,v\in QT^*\)
• Az \(A\) automata az \(u\) konfigurációt a \(v\) konfigurációra redukálja, ha

Közvetett redukció