Bevezetés az automaták elméletébe I. [antikvár]

ELŐSZÓ E jegyzet elsősorban a programozó matematikus hallgatók számára készült, akik tanulmányaik során az Eötvös Loránd Tudományegyetemen negyedéves korukban hallgatják az Automaták elmélete c. tárgyat. Figyelembe véve azonban, hogy magyar nyelven automataelméleti könyv mindeddig nem jelent meg, remélni szeretnénk, hogy haszonnal forgatják mindazok a matematikát tanuló egyetemi hallgatók, akik speciálkollégiumon vagy egyéni tanulás utján ismerkednek e tárggyal. Az automaták elméletét az absztrakt algebra egyik fejezeteként tárgyaljuk, nem használunk fel azonban a modern algebrából annál mélyebb apparátust, amellyel egy másod-harmadéves hallgató már ne rendelkezne. Az automaták matematikai elmélete az elméleti kibernetika egyik fejezetének tekinthető, amely mintegy húszéves múltra tekint vissza és ma már a matematika egyik gazdag fejezete, amely részben a gyakorlatból eredő inspirációk, részben pedig az elmélet belső törvényei szerint fejlődik. A jegyzetben távolról sem törekedhettünk teljességre, csupán arra vállalkozhattunk, hogy bepillantást adjunk az automaták (elsősorban a véges automaták) elméletének néhány fejezetébe és az automataelméletben hatásos módszerek egy részébe. A jegyzet három kötetben fog megjelenni. A jelen I. kötetben az automaták, főként a véges automaták, majd röviden az általánositott szekvenciális gépek által realizálható információátalakitásokat vizsgáljuk, a véges automaták által felismerhető nyelvek egy nem grammatikával történő leirását adjuk és egy algebrai számitőgépmodellt ismertetünk. A később megjelenő II. kötet az automatákat mint nyelvfelismerő rendszereket vizsgálja és az automaták egy olyan hierarchiáját épiti ki, amely megfelel a formális nyelvek Chomsky-féle hierarchiájának. Emellett foglalkozni fog az automatafogalom egy olyan általánosításával, amely grammatikákban való levezetések felismerésére alkalmas. Itt jegyezzük meg, hogy a jegyzet a formális nyelvek elméletéből csupán olyan kérdéseket tárgyal, amelyek szükségesek az automataelmélet kiépítéséhez, de annak ellenére, hogy a formális grammatikák elmélete szoros kapcsolatban van az automataelmélettel, már csak terjedelmi okok miatt is, nem vállalkozhat a matematikai nyelvészet e számítástudományban oly fontos területének részletes bemutatására. E területen a hallgatónak jő tájékoztatást nyújt Révész György Bevezetés a formális nyelvek elméletébe c. jegyzete, a gyakorlati alkalmazásokat illetően pedig Varga László Rendszerprogramozás I-III. cimü jegyzete. Mi a Chomsky-féle hierarchia nyelvosztályai közül a 3-as tipusu vagy reguláris nyelvek osztályával és annak bizonyos részosztályaival foglalkozunk részletesen. - 5 -