|
|
|
|
Alcím:
|
Algebraic theory of languages and codes
|
|
Téma:
|
Matematika
|
|
Pályázat:
|
TÁMOP 0064 - BME
|
|
Ismertető:
|
A jegyzetben sok évi oktatási tapasztalat összegződik. Tartalmazzák a Budapesti Műszaki és Gazdaságtudományi Egyetem Természettudományi Karának alkalmazott matematikus szakán tartott Formális rendszerek négyféléves témacsoport utolsó három félévének anyagát, de ennél jóval bővebb terjedelműek. A kötetek egyfajta bevezetést adnak az automaták, a formális nyelvek és a változó hosszúságú kódok algebrai elméletébe. Az elméletbe további kiváló bevezetést nyújt a [5] elektronikus jegyzet, amely igen sok példával és feladattal segíti a terület tökéletes megértését. A terület egy rövid világos áttekintését adja a [7] elektronikus jegyzet. A jegyzethez csatlakozik a sok feladatot tartalmazó [8] elektronikus példatár. Minthogy a [5] és a [8] jegyzetek már mindenki számára hozzáférhetők, ezért szükségtelennek tartottuk, hogy a jelen jegyzet nagyon sok feladatot tartalmazzon. A fejezetek többsége végén azonban mégis vannak feladatok, amelyek remélhetőleg teljesebbé teszik az előbb említett két jegyzet, valamint a [1] jegyzetünk feladatgyűjteményét. A jegyzet alig tartalmaz automatákkal kapcsolatos feladatot, mivel ilyen jellegű feladatok sokasága található a [1] jegyzetünkben is. A feladatokhoz általában megoldási útmutatót adunk. Sok esetben közöljük a teljes megoldást.
A jegyzetünkben is felhasznált halmazelméleti és algebrai fogalmakat és tételeket Az Algebrai Automataelmélet elektronikus jegyzetünk Függelékében foglaltuk össze. A Tárgymutató ezeket az adatokat nem tartalmazza. A lineáris algebra, a számelmélet és a kombinatorika alapfogalmait és alapvető eredményeit azonban most is ismertnek tételezzük fel.
Megemlítjük, hogy algoritmikusan megoldható és megoldhatatlan problémákkal is foglalkozunk. Az algoritmus matematikai fogalmára nincs egységes, mindenki számára elfogadott definíció. A számunkra megfelelő algoritmus fogalmának kialakításához közelítsük meg először a matematikai eljárás fogalmát Révész György segítségével. A [15] alapműnek is tekinthető munkájában a következőket írja:
Az olyan módszert nevezzük matematikai értelemben eljárásnak, amelynek minden részlete teljes pontossággal előre ki van dolgozva, tehát menet közben további gondolkodást nem igényel. Ez végeredményben azt jelenti, hogy minden eljárást elvileg egy számítógépbe be lehet programozni.
|
|
|
|
Szerzők:
|
Babcsányi István
|
|
|
|
Kulcsszavak:
|
véges automaták
formális nyelvek
Parikh függvények
Geffert normálformák
Automaták
Sardinas-Patterson kritérium
Formális rendszerek
Turing automaták
Greibach normálforma
Chomsky normálforma
Veremautomata
|
|
|
|
Szakok:
|
Alkalmazott matematikus MSC -> Alkalmazott analízis modul
|
|
|
|
|
Ajtay János
30. Algebrai nyelv- és kódelmélet