Mennyire ismered a nyelvosztályokat?

Gráf

Az élek olyan csoportja, amelyek a kiindulópontjukban és végpontjukban is ugyanazt a csomópontot érintik.

Olyan gráfot, amelyben nem találhatóak hurokélek és párhuzamos élek.

Mindegyik módon

A fej átírhatja a bemeneti értékeket.

Csak a verem tetején lévő elemekhez férhetünk hozzá.

A veremautomaták mindig a verem tetejére pakolnak.

2-es

Jobbreguláris nyelvtan

Olyan rendszer, amely egy külső inger hatására valamilyen válasszal reagál

Q,epsilon,fi,a0,F

Az irányított gráfokban minden élnek iránya van.

A páros gráfokban a csúcsokat két halmazra lehet osztani úgy, hogy az összes élnek igaz legyen, hogy az egyik végpontja A-ban van a másik pedig B-ben.

Egy gráf összefüggő, ha bármely két csomópont között létezik egy út.

Az út a csúcsok és élek egymást követő sorozata, ahol csúccsal kezdünk és csúccsal is végzünk.

Egy olyan gráf, amelynek bármely két csúcsát pontosan egy él köt össze.

A környezetfüggő nyelvtanok olyan nyelvtanok, amelyek csak lineáris idejű feldolgozással fogadhatók el. A lineáris idejű feldolgozás pedig olyan feldolgozási modellt jelent, ahol a bemeneti szalag feje nem csak olvasó, hanem író is, és előre-hátra tud mozogni a bemeneti szalagon.

A veremautomaták egy véges automatából és egy veremből állnak. A verem tetejére pakolunk, törlés során pedig mindig csak a verem tetején lévő elemekhez férünk hozzá. A veremautomaták akkor is válthatnak állapotot, ha a bemeneti szóban nincs előrelépés. A hagyományos, véges automaták általában nem használnak vermet és csak akkor változtatnak állapotot, ha az aktuális bemeneti szimbólum feldolgozásra került.

A veremautomaták alkalmasak a környezetfüggetlen nyelvek felismerésére. A veremautomaták verme lehetőséget ad arra, hogy a nyelvtan szabályait rekurzívan alkalmazni tudjuk, így az ilyen nyelvek felismerése hatékonyan megoldható velük.

Az irányított gráfokban minden élnek iránya van, míg az irányítatlan gráfokban az élek nem rendelkeznek iránnyal és a két csomópont közötti út ugyanaz, függetlenül attól, hogy melyik csomópontból indulunk.

A teljes gráf olyan gráf, amelyben minden csomópontból vezet legalább egy él egy másikba, tehát az élek száma maximális.

Chomsky négy nyelvosztályba sorolta a nyelvtanokat: a reguláris, a környezetfüggetlen, a környezetérzékeny és a rekurzív felsoroló nyelvtanokat. Ezek közül a legmagasabb fokú nyelvosztály a rekurzív felsoroló nyelvtan, amelynek segítségével bármilyen számítási probléma megoldható, azonban ennek a nyelvtannak a leírása rendkívül bonyolult.

A 0-ás, 1-es, 2-es és 3-as nyelvosztályokat említi a szöveg. A legnagyobb sorszámú nyelvosztály (3-as) jelöli a legszigorúbb, míg a legkisebb (0-ás) a kevésbé szigorú megszorításokat. Az 1-es nyelvosztályba tartoznak a környezetfüggő nyelvek; a szabályuk: BAy -> Bay. A 2-es nyelvosztályba tartoznak a környezetfüggetlen nyelvek; a szabályuk: A -> a. Az 3-as nyelvosztályba tartoznak a jobbreguláris nyelvek; a szabályuk: A -> aB, vagy A -> a.

A véges automata definíciója: M = {Q,epszilon, fi, a0, F}. Q az automata állapotait jelenti, epszilon az automata ábécéjét, fi az automata állapotváltásainak szabályait, a0 az automata kezdőállapotát, F az automata elfogadó állapotainak halmazát jelenti. Az automatának véges számú állapota van, amelyek közül pontosan egy állapot az induló állapot, és lehetnek elfogadó állapotok is. Az állapotok közötti átmenetek az ábécé betűin keresztül történnek, és az átmeneteket általában függőleges nyilak jelzik.

Az automaták olyan rendszerek, amelyek a külső ingerek hatására válasszal reagálnak. Az automatának vannak állapotai, amelyek a megadott szabályok alapján változnak a külső ingerek hatására. A véges automaták egy olyan típusa, amelynek a definíciója M = {Q,epszilon, fi, a0, F}. Az állapotok közötti átmenetek az ábécé betűin keresztül történnek, és az átmeneteket általában függőleges nyilak jelzik.

A gráf egy hálós adatszerkezet, amely élekből és csúcsokból épül fel. Minden elemnek tetszőleges számú megelőzője és tetszőleges számú rákövetkezője van. Egy elem lehet a másiknak megelőzője, rákövetkezője(saját magának is).

Egy gráfot megadhatunk egy ábra formájában, ahol a pontok vagy betűk felelnek meg a csúcsoknak és az őket összekötő ívek pedig a gráf éleinek felelnek meg. Egy másik megadási mód például, hogy csak egyszerűen felsoroljuk a csúcsokat és az éleket, vagy akár egy listában is tárolhatjuk ezeket. Minden csúcshoz eltároljuk a rákövetkezőjét és a megelőzőjét.

Egy egyszerű gráf olyan gráf, amelyben nem találhatóak hurokélek és párhuzamos élek. Hurokél azokat az éleket nevezzük, amelynek a kiindulópontja és a végpontja is ugyanaz a csomópont.