2.2. Nyelvműveletek

Két nyelv között akkor értelmezhetünk valamilyen műveletet, ha ugyanazon V ábécé felett vannak értelmezve. (Ha ez nem teljesül, akkor először a nyelveket kell átdefiniálni formálisan egy közös ábécé, pl. a két ábécé uniója felettire.)

Formális nyelvekre, mint szóhalmazokra közvetlenül értelmezhetők a halmazelméleti alapműveletek:

unió (egyesítés, összeadás): L 1L 2 = { p | p ∈ L 1 vagy p ∈ L 2},

metszet: L 1L 2 = { p | p ∈ L 1 és p ∈ L 2},

különbség: L 1L 2 = { p | p ∈ L 1 és pL 2},

komplementer: = V *L 1.

Amint látjuk a komplementerképzésnél nagyon fontos az alaphalmaz, vagyis az ábécé ismerete, hiszen pl. az L = { ab, aa, ba, bb } nyelv komplementere telejsen más, ha L- et a V = { a, b}, vagy a V ' = { a, b, c } ábécé felettinek definiáltuk. Ennek megfelelően a továbbiakban is mindig úgy tekintünk egy nyelvre, mint egy adott V ábécé feletti nyelvre (akkor is ha ezt a tömörség kedvéért nem írjuk oda).

A nyelveken a halmazműveleteken kívül a konkatenációt és az iterációt alapműveleteknek tekintjük: Két nyelv konkatenációján a következő nyelvet értjük: L 1L 2 = { pq | p ∈ L 1 és q ∈ L 2}. Szokásos módon a konkatenáció jelét sokszor elhagyjuk, pl. L 1 L 2. Legyen i = 1, 2, …. Ekkor egy L nyelv i-edik hatványán a nyelv i-szer egymás utáni, önmagával való konkatenációját értjük. Jelölés: L i . Megállapodás szerint L 0 = { λ}.

A konkatenáció lezárását (Kleene iterációt) (ejtsd: klíni) az összefüggéssel értelmezzük.

Az előző Kleene-csillag művelet mellett szokás még az iteráció, a Kleene-plusz használata is.

A kétféle iteráció között az L 0 = { λ } jelenthet különbéget: A definiáló egyenlőségek alaján belátható, hogy L + = L * pontosan akkor, ha λ ∈ L. Továbbá L + = L * ∖ { λ } pontosan akkor, ha λL.

Mejegyzés. Mivel a V ábécé mint halmaz egyben tekinthető egy formális nyelvnek is, a korábbi V * és a V + jelölés éppen egybeesik a most definiált iteráció műveletek V-re való alkalmazásának eredményével.

Legyen V ábécé rögzített, ekkor igazak az alábbi összefüggések (tetszőleges L 1, L 2, L 3V * esetén):

Az unió, metszet, illetve konkatenáció asszociativitása miatt általában nem is szoktuk zárójelekkel jelezni a műveleti sorrendjüket, így egyszerűen pl. L 1L 2L 3 alakot használunk.

További zárójeleket hagyhatunk el megtartva az egyértelmű jelentést a követekező precedencia reláció bevezetésével. Az egyargumentumú műveletek (komplementer, (Kleene-)csillag és (Kleene-)plusz) precedenciája nagyobb, mint a kétargumentumúaké. A szorzás (konkatenáció) precedenciája nagyobb, mint az unió és metszet műveleteké.

Legyen adva két véges ábécé, V 1 és V 2. A V 1 *-nak a V 2 *-ba való h leképezését homomorfizmusnak nevezzük, ha:

A fenti két tulajdonságból rögtön következik, hogy az üresszó képe az üresszó lesz, ugyanis h ( p ) = h ( p λ ) = h ( p ) h ( λ ) minden pV 1 * szóra.

Egy homomorf leképezést λ- mentesnek nevezünk, ha h ( p ) = λ esetén p = λ.

2.7. példa - Nyelvműveletek - Gyakorló feladat

Legyen V = { a, b, c}, L 1 = { a, c, bb, aba}, L 2 = { a, abba, baba, caba, abbaba, babaabba}. Adjuk meg az L 1L 2, L 1L 2, L 1 L 2, L 1 L 1 halmazokat. ★


2.8. példa - Nyelvek konkatenációja

Adjunk példát olyan L 1 és L 2 V ábécé feletti nyelvekre, amelyekre L 1 L 2 = L 2 L 1. Keressünk nem triviális megoldást is.


Triviális megoldások:

Egy nem triviális megoldás:

legyen V = { a, b}, L 1 = { λ, a}, L 2 pedig legyen azon V feletti szavak halmaza, amelyekben pontosan egy b szerepel. Ekkor L 1 L 2 = L 2 L 1 = L 2. ★

2.9. példa - Nyelvek számossága - Gyakorló feladat

Adottak L 1 és L 2 véges nyelvek V ábécé felett, hogy | L 1 | = n, | L 2 | = m. Mennyi lehet a számossága az L 1L 2, L 1L 2, L 1 L 2 nyelvműveletekkel előálló nyelveknek? Adjunk meg alsó felső korlátot, és példákat. ★


2.10. példa - Formális nyelvek, nyelvműveletek 1.feladat

Igazoljuk vagy cáfoljuk, hogy (L 1L 2 )* = L 1 *L 2 * !

Megoldás: Az állítás hamis. Vegyük a következő ellenpéldát: Legyen L 1 = { a} és L 2 = { b}, ekkor ( L 1L 2 )* az akárhány a-t és b-t tartalmazó szavak halmaza, még L 1 *L 2 * a csupa a-t és csupa b-t tartalmazó szavak nyelve lesz. ★


2.11. példa - Formális nyelvek, nyelvműveletek 2.feladat

Mivel egyenlő L 2, ha

L = { a n b n |n >0 } ?

Megoldás: L 2 = { a n b n a m b m | n, m > 0}. ★