Chapter 2. Formális nyelvek

Ahogy általában a programokat, úgy az algoritmusokat is jellemzően nem egy konkrét feladat, hanem egy feladatcsoport megoldására alkotjuk. Az algoritmus bemenetét, kimenetét illetve más kapcsolódó objektumokat (pl. magát az algoritmust is) valamilyen általános módon szeretnénk megadni, kezelni. Ehhez szükségünk lesz néhány alapvető fogalomra és eredményre a formális nyelvek elméletéből.

Először következzen néhány függvényekkel kapcsolatos fogalom.

2.1. Definíció

Legyen  és  két tetszőleges nem üres halmaz. 
A két halmaz Descartes-szorzatán az  párokból álló
halmazt értjük. Ha , akkor az  jelölést is használhatjuk.

Legyen . Az  halmazt az -n értelmezett relációnak nevezzük. 
Ha valamilyen  és  esetén , akkor azt mondjuk, 
hogy  és  
            
                szerinti relációban van.

Legyen  egy reláció. Ha  és  
esetén  csak akkor lehet, ha , akkor -et (parciális)
függvénynek nevezzük és -vel jelöljük, illetve ha ,
akkor a hagyományos  jelölést használjuk.
Ha  amelyikre , akkor totális függvénynek
nevezzük. 

Legyen  egy totális függvény. Ha  esetén amelyikre
 , akkor -et szürjektív leképezésnek vagy ráképezésnek nevezzük.
Amennyiben  esetén -ből következik, hogy , 
akkor -et injektív leképezésnek vagy egy-egy értelmű leképezésnek 
nevezzük.
Ha  szürjektív és injektív is, akkor bijektívnek nevezzük.

2.2. Megjegyzés

Az  reláció esetén a hagyományos jelölés , ahogy például 
a  és  relációknál megszoktuk.

Ha  és  két függvény, akkor értelmezhetjük az uniójukat, 
 mint relációk unióját. Ez azonban nem lesz feltétlenül 
újabb függvény. Amennyiben feltesszük, hogy , akkor már  is 
függvény, amire .

Mivel a későbbiek során azt szeretnénk igazolni, hogy a felépített algoritmusfogalmunk matematikai szempontból precízen megadható, ezért szükség van az ábécé, szó és nyelv pontos, a szemléletestől eltérő, de minden részletre kiterjedő definíciójára. Erre azért is van különösen nagy szükség, hogy az üres jelnek nevezett szimbólum helyét megtaláljuk a rendszerben.

2.3. Definíció

Ábécé: a   véges nem üres halmazt ábécének nevezzük. 
  elemeit betűknek (időnként jeleknek) nevezzük.
Amennyiben , akkor -re megköveteljük, hogy  legyen. 
(A továbbiakban -t üres jelnek nevezzük.)

2.4. Definíció

Legyen  egy nem üres halmaz és  egy leképezés  
esetén.

Ha -re teljesülnek a következők:
1. ; 
2.  betűre igaz, hogy  amire ;
3.  és  esetén , akkor 
   és csak akkor, ha  és ; (lehet, hogy elegendő az "akkor")
4.  esetén,  és , 
   amelyikre ; (Ez lehet, hogy 5-ból következik.)
5. (Teljes indukció.) Legyen  egy állítás  elemein. 
   Ha  igaz és  esetén -ből következik , 
   akkor  esetén igaz ;
6. Ha  , akkor  
            ;
   akkor -t a  ábécé fölötti véges szavak halmazának és -t 
   az üres szónak nevezzük. 

A hagyományoknak megfelelően használni fogjuk a  és 
a  jelölést.

2.5. Megjegyzés

1. Legyen . A  leképezést egyszerűen úgy értelmezhetjük, 
   hogy -t -ből egy  betű hozzáírásával kapjuk. 
2. A  és  halmazok között megadható egy  természetes 
   beágyazás, ahol .
   Ennek megfelelően a  halmaz elemei tekinthetők a  halmaz 
   elemeiből álló véges hosszúságú sorozatoknak.
3. Az előző definíció 6. pontja alapján , azaz  és  különbözőek, 
   de a két halmazban egymásnak megfeleltethetők.
4. A definíció 6. pontja alapján a 3. pontját kiterjeszthetjük 
   az  és  esetekre is.
5. Az 5. pont lényegében azt jelenti, hogy minden szó előállítható 
   az üres szóból betűk hozzáadogatásával.
   Ilyen módon, amennyiben , ahol , 
   akkor a szót jelölhetjük a szokásos módon  alakkal is.
6. A 3. pont alapján az előbbi előállítás egyértelmű.
7. Az előző pontot kiterjeszthetjük az üres jelre is, 
    tulajdonsággal.

2.6. Definíció

Legyen  függvény a következő tulajdonságokkal:
1. ;
2. ,  és  esetén.
Ekkor az  értéket a  
         szó hosszának nevezzük.

2.7. Tétel

             esetén  értéke egyértelműen definiált.

Bizonyítás

Egy szó hossza a definíció alapján azt jelenti, hogy hányszor kellett leképezést alkalmazni az üres szóra, hogy megkapjuk -t. Mivel a szó előállítása során a valódi bővítő lépések darabszáma és sorrendje rögzített, hosszára egyértelmű értéket kapunk. ✓

2.8. Megjegyzés

Belátható,hogy amennyiben egy szót véges jelsorozatnak tekintünk, 
a hossza pontosan a benne szereplő jelek számával egyezik meg.

2.9. Definíció

Legyen  egy kétváltozós művelet -on, azaz: ⋅:, a következő 
tulajdonságokkal:
1.  legyen ;
2.  és  esetén .
Ekkor  -t az összefűzés (más néven konkatenáció) műveletének nevezzük.
A hagyományoknak megfelelően a  jelölés helyett gyakran az 
egyszerűbb  írásmódot választjuk.

2.10. Tétel

A konkatenáció műveletére igaz, hogy  esetén, ha  és 
, akkor .

Bizonyítás

A bizonyítást -re vonatkozó teljes indukcióval végezzük.

a.) A definíció alapján, ha , azaz , akkor az állítás igaz.

b.) Tegyük fel, hogy egy adott esetén minden szóra, ha , akkor az állítás igaz.

Legyen egy hosszú szó. Ha utolsó betűje , akkor valamilyen -re, ahol .

Az indukciós feltevés szerint . Felhasználva az összefűzés definícióját,

ami azt jelenti, hogy az állítás -re is igaz.

a.)-ból és b.)-ből teljes indukcióval következik az állítás. ✓

2.11. Tétel

          a konkatenációval, mint kétváltozós művelettel egységelemes 
félcsoportot alkot. 

Bizonyítás

A bizonyítást teljes indukcióval végezzük.

1. A konkatenáció asszociatív:

a.) Definíció szerint .

b.) Tegyük fel, hogy egy adott esetén minden szóra, ha, akkor igaz az asszociativitás. Legyen olyan, hogy . Ekkor és amelyikre és . Az indukciós feltevés alapján minden szóra igaz, hogy . Ez alapján

,

ami azt jelenti, hogy -re is igaz az állítás.

a.)-ból és b.)-ből teljes indukcióval következik az asszociativitás.

2. egységelem. Definíció szerint minden esetén.

Azt, hogy , teljes indukcióval bizonyíthatjuk.

a.) Definíció szerint .

b.) Tegyük fel, hogy minden esetén, ha , akkor . Legyen egy hosszúságú szó. Ekkor és , amire és . Az indukciós feltevés alapján

,

ami azt jelenti, hogy az állítás -re is igaz.

a.)-ból és b.)-ből teljes indukcióval következik .

Ezzel a tételt beláttuk. ✓

2.12. Tétel

A konkatenáció műveletére érvényes az egyszerűsítési szabály, azaz 
 esetén -ből következik . 
Hasonlóan -ből következik 
      

Bizonyítás

A bizonyítást az előzőekhez hasonlóan teljes indukcióval végezhetjük. Az első esetben -re, a második esetben pedig -re és -re egyidejűleg. ✓

Szavak szerkezetének leírására hasznosak a következő definíciók.

2.13. Definíció

Legyen  olyan, hogy . 
Ekkor -t a  egy kezdőszeletének, -t pedig egy zárószeletének 
nevezzük.

2.14. Megjegyzés

Egy szó saját magának triviális kezdő- és zárószelete.
Az üres szó minden szónak triviális kezdő- és zárószelete.

A véges szavak halmazán megadhatunk alakú transzformációkat. Ezek rendelkezhetnek bizonyos jó tulajdonságokkal. Néhány a legfontosabbak közül a következőképpen adható meg.

2.15. Definíció

Egy  alakú transzformációt hossztartónak nevezünk, 
ha  esetén .

2.16. Megjegyzés

Hossztartó leképezés például a tükrözés, betűpermutáció, ciklikus 
permutáció, stb.

2.17. Definíció

Egy  alakú transzformációt kezdőszelettartónak nevezünk, 
ha  esetén  amelyikre .

2.18. Megjegyzés

Az előző példák közül a tükrözés és ciklikus permutáció nem, viszont 
a betűpermutáció kezdőszelettartó.
Kezdőszelettartó, viszont nem hossztartó például a következő 
transzformáció: . (Ismétlés.)

A szavak fogalmát felhasználva az algoritmusok szempontjából fontos objektum meghatározásához érkeztünk.

2.19. Definíció

Legyen  egy véges ábécé. Az  halmazt egy  fölötti (formális) 
nyelvnek nevezünk.

Nyelveken értelmezhetjük a hagyományos halmazműveleteket, pl. ha két nyelv, akkor az és is az. Az nyelvet az komplementerének nevezzük.

Ezeken kívül kiemelt szerepűek a következő nyelvműveletek.

2.20. Definíció

Legyen  két nyelv. Az  nyelvet a két 
nyelv összefűzésével nyert nyelvnek nevezzük és -vel jelöljük.

2.21. Megjegyzés

Ha az  nyelvet saját magával fűzzük össze, használhatjuk a következő 
egyszerűsített jelölést:
 és , ha .

2.22. Definíció

Legyen  egy nyelv. Az  nyelvet az  
            iteráltjának, 
vagy más néven a konkatenációra vett lezártjának nevezzük.

2.23. Megjegyzés

A lezárt elnevezés abból a tényből ered, hogy  pontosan az a 
legszűkebb nyelv, amelyiknek részhalmaza  és nem vezet ki belőle 
az összefűzés művelete.

2.24. Definíció

Legyen  nyelveknek egy osztálya. 
Ekkor }. Itt  az  nyelv komplementerét jelöli.

2.25. Megjegyzés

          nem a  komplementerét jelöli. Olyannyira nem, hogy  
nem feltétlenül üres. Ha pl.  az összes nyelv osztálya, akkor .

2.26. Tétel

Legyen  és  két ugyanazon ábécé fölötti nyelvek osztálya. 
Ekkor 
1. ;
2. ;
3. ;
4.  akkor és csak akkor, ha .

Bizonyítás

Szokásos halmazelméleti egyenlőségbizonyításokkal dolgozhatunk.

1. Felírhatjuk a következő ekvivalencialáncot:

vagy vagy .

2. Az előzőhöz teljesen hasonlóan felírhatjuk a következő ekvivalencialáncot:

és és .

3. Ebben az esetben a következő írhatjuk:

.

4. Definíció szerint akkor és csak akkor, ha és akkor és csak akkor, ha . Definíció szerint akkor és csak akkor, ha -ból következik . Az előzőek alapján ez pontosan akkor áll fenn, ha -ból következik . ✓