1. fejezet - Bevezetés

Az algoritmikus szemlélet kialakulására nagy hatással volt az 1900-ban Párizsban rendezett első matematikai világkongresszus, ahol is többek között elhangzott David Hilbert híres előadása, melynek hatására tág teret kapott az absztrakt gondolkodásmód széleskörű alkalmazása.

Hilbert még úgy vélte, hogy létezik olyan univerzális módszer, melynek segítségével minden matematikai kérdés igaz vagy hamis volta eldönthető.

A modern elméleti számítástudomány egyik fontos fogalma a formális rendszer, melynek bevezetése Axel Thue (ejtsd: tyué) nevéhez fűződik, aki az 1910-es évek elején kezdte tanulmányozni az adatsorozatokkal megadott utasítások tulajdonságainak vizsgálatát.

A fejlődésnek e téren is újabb lökést adtak a fiatal Kurt Gödel felfedezései, aki a 20-as, illetve 30-as években kimutatta, hogy létezik olyan precízen megfogalmazható matematikai állítás, melynek sem igaz, sem hamis volta nem bizonyítható. Ez a korszakalkotó felfedezés alapjaiban rengette meg a matematikát. Ezután már senki sem lehetett biztos abban, hogy egy tetszőlegesen kiválasztott matematikai állítás igaz vagy hamis voltának eldöntése lehetséges. Erre csattanós példa volt az ugyancsak ifjú Jurij V. Matijaszevics esete, aki a 70-es évek elején kimutatta Hilbert már említett híres előadásában szereplő egyik kérdésről, hogy eldönthetetlen. (Hilbert 10. problémája.)

A 30-as évek második felében egy másik fiatal óriás, Alan Turing (ejtsd: tyuring) vizsgálataival párhuzamosan, Alonzo Church (ejtsd: csörcs) kapott hasonló módon meglepő eredményt. Nevezetesen, hogy nem létezik univerzális feladatmegoldó módszer.

A gépies bizonyítások vizsgálata elvezetett az automaták matematikai elméletének 50-es évekre kialakult megalapozásához, az idegen szövegek gépi fordításának vizsgálata pedig ugyancsak az 50-es években a formális rendszerek egy fontos típusa, a formális nyelvek matematikai elméletének kezdeteihez. Ezen a területen Noam Chomsky (ejtsd: csomszki) alapvető felfedezései jelentettek nagy lépéseket.

Végül, de nem utolsósorban meg kell említenünk, hogy az automaták matematikai elméletének megalapozásában nagy szerepet játszott a pályafutásának nagy részét az Egyesült Államokban töltő magyar származású nagy tudós, Neumann János, aki John von Neumann néven szerte a világon mint a számítástudomány atyja ismeretes. 1960-ban bekövetkezett korai halála sajnos megakadályozta abban, hogy az e téren (is) végzett úttörő kutatásait teljeskörűen megalapozza.

Már Neumann János is látta, hogy a bonyolultság és az azzal kapcsolatos kérdések nagy szerepet fognak játszani a számítástudományban. Valóban, a számítógépek 60-as évektől bekövetkezett széleskörű elterjedésével mind az elméleti, mind pedig a gyakorlati szakemberek azt tapasztalták, hogy bizonyos kérdéseket még a legmodernebb számítástechnikai eszközök felhasználásával sem képesek kezelni. Ezek a problémák nemcsak elméleti, hanem nagyon fontos gyakorlati feladatokkal kapcsolatban is felléptek. Hamarosan kiderült, hogy ez a gond nem fog megoldódni a számítógépek rohamos fejlődésével sem, mivel valószínűleg elvi akadályokról van szó. A kérdéses feladatok túl bonyolultnak látszanak ahhoz hogy kezelni tudjuk őket. A 70-es évek elején ezen kérdések kezelésére Stephen A. Cook (ejtsd: kuk), Richard M. Karp és Leonid A. Levin egy új elmélet megalapozását kezdeményezték. Megszületett az algoritmusok bonyolultságelmélete. Az eltelt több mint 30 év alatt azonban sajnos ez az elmélet nem adott választ a feltett legégetőbb kérdésekre. Ezek közül is a legfontosabb, az úgynevezett P = NP? probléma, melynek megoldása választ adna arra a nagyon fontos kérdésre, hogy egyes, a gyakorlatban is lépten-nyomon felmerülő feladatokhoz létezik-e hatékony megoldó algoritmus. Ez a több mint 30 éves nagy kérdés valószínűleg még sokáig megoldatlan marad.

A bonyolultságelmélet által felvetett problémák a 80-as évek közepére-végére elvezettek egy új terület, az úgynevezett kooperatív rendszerek megszületéséhez. Kezdetben csak arról volt szó, hogy olyan számítástechnikai eszközök születtek, melyek egyes feladatok egyidejű, párhuzamos végrehajtására voltak képesek. Ma már a kooperatív rendszerek széleskörűen elterjedtek és mind elméleti, mind pedig gyakorlati szempontból egyre nagyobb teret kapnak olyan berendezések és módszerek, amik eddig nem, vagy csak csekély mértékben voltak használatosak. Talán ezen az úton haladva fogunk eredményt elérni a még mindig megközelíthetetlennek látszó problémák kezelésében.

A formális nyelvek és automaták elmélete kiváló eszköznek bizonyult ezen kérdések absztrakt szintű vizsgálatában. Jelen jegyzet célja ezen elmélet legalapvetőbb kérdéseinek megismertetése. Az ismertetett módszerek ma már lépten-nyomon használatosak nemcsak elméleti problémák vizsgálatában, hanem egyes gyakorlati számítástechnikai feladatok megoldásában is. A formális nyelvek és automaták elmélete nemcsak olyan kézenfekvő területeken nyert alkalmazást, mint a számítógépes nyelvészet, illetve a fordítóprogramok területe, hanem ezen keresztül a programozási nyelvek, operációs rendszerek témakörében is. Például a sztringalgoritmusokon keresztül keresőalgoritmusokban, bioinformatikában, mintaillesztésben, adatbányászatban stb. is alkalmazzák. A biológiailag motivált számítások, a DNS és membrán számítások formális modelljei szintén erősen kötődnek a formális nyelvek és automaták klasszikus elméletéhez. A képfeldolgozásban, adatsűrítésben, rendszermodellezésben szintén felhasználhatjuk az itt tanultakat. Helyenként nagy figyelmet fordítunk annak igazolására is, hogy bizonyos struktúrák és módszerek nem léteznek, illetve nem lehetségesek. Ez a fáradtság a gyakorlati számítástechnikai szakember számára feleslegesnek tűnik. Jelen jegyzet szerzői, akik egyike több mint másfél évtizedig gyakorlati számítástechnikai szakemberként dolgozott, másképp gondolják. Ha ismerjük a leggyakoribb számítástechnikai zsákutcákat, akkor könnyebben ki tudjuk kerülni azokat. Ha nem, akkor úgy járhatunk mint ahogy a jegyzet nevezett szerzője is járt nem egy esetben: esetleg olyat próbálunk keresni, amiről már kiderült, hogy nincs.

Jelen jegyzet elméleti fejezeteit Dömösi Pál (pl. Automataelmélet) és Nagy Benedek (pl. Lineáris nyelvek, Környezetfüggő nyelvek, Nyelvtanrendszerek) írták (a többi fejezetet együttesen). A feladatok döntő többségét és az animációkat Falucskai János, Horváth Géza és Mecsei Zoltán készítették.

A feladatok, példák és definíciók végét a ★ jellel jelöljük. A bizonyítások végét pedig ∎-el zárjuk.

A jegyzet egyes főbb fejezeteinek felépítése a következő összefoglaló segítségével is követhető:

Nyelvosztály Nyelvtan Normálformák Automataosztály Szóprobléma Zártsági tulajdonságok Egyéb



                           
                              Reguláris nyelvek
                           

Chomsky 3. típus
pl: egész számok halmaza
Alosztályok:
    - véges nyelvek
    - uniómentes nyelvek


- jobb-lineáris :
    A → uB
    
                           A → u
- bal-lineáris:
    A → Bu
    
                           A → u

                           A,B ∈ N

                           u ∈ T
                           *

                        


gyenge:
    A → aB
    
                           A → a
    
                           A → B
    
                           A → λ
erős:
    A → aB
    
                           A → a

                           a ∈ T

                           A,B ∈ N

                        



                           véges automaták:
nemdeterminisztikus
    üresszóátmenetes

nemdeterminisztikus
determinisztikus parciális
determinisztikus
    teljesen definiált

Minimális determinisztikus
  automata: Myhill-Nerode tétel
Kapcsolódó terület:
    Automataelmélet

                        


determinisztikusan,
    lineáris időben
    megoldható



                           
zárt a reguláris- és
 a halmazműveletekre


                        


alternatív leírás:
  - reguláris kifejezés
  - szintaxis gráf

                           pumpáló lemma

                        



                           
                              Lineáris nyelvek
                           

pl: palindrómák nyelve
Alosztályok:
  - Determinisztikus
     automatával:
      2detLin
      
                           detLin
  - Fix fokú lineáris:
       k-fokú lineáris
  bal-, ill. jobb-lineáris
Kiterjesztés:
    - metalineáris nyelvek



                           A → uBv

                           A → u

                           A,B ∈ N

                           u,vT
                           *

                        


gyenge:
    A → aB
    
                           A → Ba
    
                           A → a
    
                           A → B
    
                           A → λ
erős:
    A → aB
    
                           A → Ba
    
                           A → a

                        


- determinisztikusan
    négyzetes
    algoritmus
- nemdeterminiszti-
  kusan
    lineáris



                           pumpáló lemma

                        



                           
                              Környezetfüggetlen
                           

Chomsky 2. típusú
pl: Zárójelek nyelve 
Alosztályok:
    - determinisztikus CF
    - számlálónyelvek
Kiterjesztés: pl. CD és
    PC rendszerek


                        



                           A → p

                           A ∈ N

                           p ∈ ( NT )*

                        


Chomsky:
    A → BC
    
                           A → a
Greibach:
    A → aq

                           A,B,C ∈ N

                           a ∈ T

                           q ∈ N
                           *

                        



                           nemdeterminisztikus
  veremautomata

    - üres veremmel
    - végállapottal
    - üresveremmel és
        végállapottal
    - állapotnélküli
        (üres veremmel)


                        


CYKEarley
  algoritmusok
  determinisztikus
  köbös
  időben
- nemdeterminiszti-
   kusan
   lineáris időben
   (Greibach NF)



                           
-zárt:
  reguláris műveletekre
  (unió, konkatenáció,
  Kleene-csillag)
-nem zárt:
  metszetre és
   komplementerre


                        


pumpáló lemma
    (Bar-Hillel lemma)
Levezetési fa fogalma
Legbaloldalibb
    levezetés

alternatív leírás:
  BNF, szintaxis gráf

                        

Nyelvosztály Nyelvtan Normálformák Automataosztály Szóprobléma Zártsági tulajdonságok Egyéb



                           
                              Környezetfüggő
                           

Chomsky 1. típusú
pl: prímszámhosszú
    szavak nyelve

Alternatív definíció:
    Monoton
Alosztályok:
    - Permutációs
    - Növekvő
        környezetfüggő


                        



                           pAq → prq

                           p,q ∈ (NT)*

                           A ∈ N

                           r ∈ (NT)+
kivéve
S → λ, de ekkor
S nem szerepelhet
egyetlen szabály
jobb oldalán sem
monoton:
 u → v
  | u  | ≤ | v  | 
 kivéve S → λ
 a fenti feltétellel



                           Kuroda:
 AB → CD
 
                           A → BC
 
                           A → B, A → a

                           Révész:
 AB → AC
 
                           AB → CB
 
                           A → BC
 
                           A → B, A → a

                           Penttonen:
 AB → AC
 
                           A → BC
 
                           A → a

                        



                           nemdeterminisztikus
 árnyékveremautomata



                           nemdeterminisztikus
 lineárisan korlátolt
 automata


                        


megoldható
(PSPACE-teljes,
 nincs hatékony
 algoritmus)



                           zárt a reguláris és a
 halmaz-műveletekre is:
    konkatenáció,
    Kleene csillag
    unió,
    metszet,
    komplementer


                        



                           Üresszó lemma
Pumpáló lemma nincs.
Levezetési gráf,
 levezetési fa és
 legbaloldalibb levezetés
 általánosítása.


                        



                           
                              Rekurzívan
    felsorolható

                           

(van olyan algoritmus,
 amivel a nyelv összes
 szava felsorolható.)
Chomsky 0. típus
Alosztály:
    Rekurzív
    (Egy nyelv rekurzív,
    ha L és L
    komplementere
    is rekurzívan
    felsorolható.)



                           generatív nyelvtan

                        



                           Révész:
 AB → AC
 
                           AB → CB
 
                           A → BC
 
                           A → B
 
                           A → a
 
                           AB → B

                           Penttonen
 
                           AB → AC
 
                           A → BC
 
                           A → a
 
                           A → λ

                           Geffert, pl:
 S → p
 
                           AB → λ
 
                           CD → λ

 
                           S → p
 
                           ABC → λ
 
                        



                           Turing gép
    - determinisztikus
    - nemdeterminisztikus
(egyéb változatok:
 több szalagos,
 csak egyirányba
  végtelen szalag)

univerzális Turing gép

kapcsolódó terület: 
kiszámíthatóság és
 bonyolultságelmélet
,
a Neumann-féle
 számítógép
 elméleti modellje


                        


algoritmikusan
 nem
 megoldható
(megállási
    probléma
)



                           tárhely tétel,
Markov algoritmus