2002/3.

Könyvszemle

Bach Iván: Formális nyelvek

A magyar szakkönyvkiadás régi adósságát törleszti a kiadó, amikor Bach Iván műegyetemi előadás-jegyzeteinek könyv formában való megjelentetésével egy sokéves oktatói gyakorlat közben formálódott anyagot ad az érdeklődő olvasó kezébe. A magyar nyelvű könyvpiacon régóta hiány van ugyanis a formális nyelvek elméletébe bevezetést nyújtó, az egyetemi oktatásban tankönyvként is használható, megfelelően széles témaválasztékot kínáló munkákban.

Meglepő és sajnálatos ez a hiány, hiszen a tudományág alapvető fogalmainak ismerete elengedhetetlen a modern számítástudomány eredményeinek megértéséhez, ezért a tárgykör oktatása mind a matematikus-, mind az informatikusképzés során fontos feladat. Ebben kíván segítséget nyújtani Bach Iván könyve.

A kötet fejezetei minden olyan témát feldolgoznak, amelyre a formális nyelvek elméletébe történő bevezetéskor szükség lehet. Áttekintést adnak a tárgykör alapfogalmairól, bemutatják a legfontosabb, ma már klasszikusnak számító tételeket, sőt, a Turing gépekkel foglalkozó fejezetben rövid betekintést nyújtanak az algoritmuselmélet alapjaiba is, mindezt rendkívül könnyen emészthető, olvasmányos formában.

Az első fejezetben a szerző bevezeti a formális nyelvekkel és generatív grammatikákkal kapcsolatos alapfogalmakat, és bemutatja a Chomsky-féle hierarchiát alkotó alapvető nyelvosztályokat, amelyekkel a későbbi részekben majd bővebben foglalkozik. A második és a harmadik fejezetben a reguláris és a környezetfüggetlen nyelvekről és a hozzájuk tartozó automata osztályokról, a véges automatákról és veremautomatákról kap az olvasó ismertetést. A következő két fejezet a véges és veremfordító automatákkal, illetve a környezetfüggetlen nyelvek szintaktikus elemzésével foglalkozik. Ez utóbbi témából a könyv az általános elemző algoritmusok mellett bemutatja a gyakorlati szempontból kiemelt fontosságú LL(k) és LR(k) típusú elemző módszerek működését is. Az utolsó fejezetben a Chomsky hierarchiát alkotó klasszikus nyelvosztályok tulajdonságainak tanulmányozásában tovább haladva az olvasó a Turing gépek világába nyerhet betekintést, ennek kapcsán felmerülnek az algoritmikus eldönthetőség és a kiszámíthatóság alapkérdései is.

A könyv erénye a matematikai szakirodalomban talán szokatlanul közvetlen, a szóbeli magyarázatok stílusát követő szemléletes előadásmód, ami azonban a tárgymutató hiánya mellett meg is nehezíti a munka tankönyvként vagy kézikönyvként való használatát. A szövegben előforduló definíciók és tételek ugyanis nincsenek külön kiemelve, ezek esetleges későbbi visszakeresése tehát fáradságos feladatnak bizonyulhat. Mindezen, egy későbbi kiadásban könnyen orvosolható hiányosságok ellenére a könyv egyaránt jó szívvel ajánlható a formális nyelvek tudományágával ismerkedő egyetemi hallgatónak és a témakör iránt érdeklődő ,,kívülálló'' olvasónak is.

Vaszil György

PhD., tud. főmunkatárs (SZTAKI)


<-- Vissza az 2002/3. szám tartalomjegyzékére