Know-how, előadás, nyelvek elmélete
A különböző nyelvtani osztályok felismerése
A nyelv meghatározása a felismerő érvényes végállapotainak megadásával történik. ha a bemeneti szalagra táplált lánc lehetővé teszi a felismerő számára, hogy végrehajtsa a lépések sorrendjét és leálljon a végső állapotban, akkor a lánc a nyelvhez tartozik.
Kiderül, hogy a Chomsky-hierarchia minden gramma osztályához tartozik egy felismerő osztály. Ugyanazon nyelvosztály meghatározása:
- Az L nyelv csak lineáris, ha és csak akkor, ha azt egy egyoldalú determinisztikus véges automata határozza meg
- Az L nyelv kontextusmentes, ha és csak akkor, ha azt egy (egyoldalú, nem meghatározó) automata tárolja
- Az L nyelv kontextusfüggő, ha és csak akkor, ha azt meghatározza (egy kétoldalú nondeterminisztikus) automata tároló memóriával
- Az L nyelv rekurzívan felsorolható, ha és csak akkor, ha azt egy Turing gép határozza meg (ezek a fogalmak nem fognak működni, hivatalosan a "Computability" vagy a "Számítástudomány" alap tanfolyamon vannak meghatározva).
Az előadás további anyaga a felismerők tulajdonságainak meghatározására szolgál. ezeket a nyilatkozatokat megemlíti, és megvitatja azok alkalmazhatóságát a gyakorlatban.
Véges állapotú gépek
A véges állapotú gép az egyik legegyszerűbb mechanizmus, amelyet a nyelvekkel való együttműködés során használnak. Ez a felismerőnek csak egy fix memóriasorozata van, és a vezérlő eszköz csak a bemeneti szalag mentén jobbra mozoghat, és megváltoztathatja a memóriaállapotokat. A véges állapotú gép fő része az átmeneti funkció. Meghatározza az esetleges átmenetek bármely aktuális állapotot és bármely bemeneti szimbólumot. Feltételezzük, hogy az automata különböző különböző állapotaiba való átmenet lehetősége megengedett, azaz az érzékelő vezérlőeszköze nem determinisztikus lehet. A meg nem határozottságot a következőképpen kell érteni: ha egy adott állapotból több átmenet egyszerre lehetséges, akkor a gépünk több példányát hoztuk létre, minden egyes új állapotot. A beszélgetést úgy kell tekinteni, hogy egy nyelvhez tartozik, ha a lépések sorainak legalább egyike a végső állapotban befejeződik.
Az alapvető ötletek ilyen rövid magyarázata után megadhatunk egy véges automata formális definícióját.
Definíció. A véges állapotú gép egy öt
- Q egy véges állapotcsoport
- - véges számú megengedett bemeneti szimbólum
- - a készlet leképezése a P (Q) halmazba. A vezérlő eszköz vezérlési viselkedését (ezt a funkciót gyakran átmeneti függvénynek hívják)
- - a vezérlőegység kezdeti állapota
- - végleges államok készlete
Elvben az állami gép későbbi lépéseinek meghatározásához elegendő ismerni a vezérlő eszköz aktuális állapotát, valamint a még feldolgozatlan szimbólumok sorát a bemeneti szalagon. Ezt az adatkészletet automaton konfigurációnak nevezik.
Determinisztikus véges állapotú gépek
Határozzuk meg a determinisztikus véges automatust egy általános (nem-determinisztikus) véges automata speciális eseteként, és hozzunk létre további definíciókat és egyezményeket, amelyek hasznosak lehetnek számunkra a jövőben:
Definíció. Az automatának azt mondják, hogy determinisztikus, ha a készlet legfeljebb egy állapotot tartalmaz bármelyik számára. Ha mindig pontosan egy állapotot tartalmaz (azaz nincs meghatározatlan átmenet), akkor az automatát teljesen meghatározónak nevezik.
Definíció. Egy ábécé fölött egy szót egy véges automata engedélyez, ha létezik egy olyan állapot sorozata, amely a.
Definíció. Az L nyelvet egy véges automata ismeri fel, ha az L nyelv minden szóját megengedik ennek a véges automatának.
Rendeltetése. A véges automatákat kényelmesen illusztrálják átmenet diagramok segítségével. lásd az alábbi példákat (a kettős körök a végső állapotokat jelölik):
Automatikus. a nyelv felismerése: Automatikus. a nyelv felismerése: