2. fejezet - Formális nyelvek

2.1. Ábécé, szó, formális nyelv, szabad monoid, szabad félcsoport

Szimbólumok tetszőleges nemüres, véges halmazát ábécének nevezzük, és V-vel jelöljük. A V elemeit az ábécé betűinek mondjuk.

Jelölje V + (ejtsd: véplusz) a V-beli betűkből felírható p=a 1 a 2ak (a 1,…,ak  ∈ V ) alakú véges hosszúságú sorozatok, az úgynevezett V feletti nem üres szavak halmazát. Egy p szó hosszát | p | -al (ejtsd p hossza) jelöljük és rajta a p-beli betűk számát értjük (esetleges többszöri előfordulással együtt). Így ha p=a 1 a 2ak (a 1,…,ak  ∈ V ), akkor | p | = k.

2.1. példa - Szó hossza

Legyen a V ábécé két betűje a és b. Ekkor babV + és | bab | = 3 (és nem 2, mert a b betű kétszer is előfordul, és a többszöri előfordulást figyelembe kell venni.) ★


Szokás beszélni az úgynevezett üresszóról is, ami egy matematikai absztrakció, ugyanis olyan szót jelent, melynek egyetlen betűje sincs, vagyis az egyetlen betűt sem tartalmazó betűsorozatot. Speciálisan, jelölje λ a továbbiakban az üresszót. Itt jegyezzük meg hogy bár az automataelméleti szakirodalomban az ε-t (is) szokás az üresszó jelölésére használni, ebben a jegyzetben mi végig a λ jelet fogjuk használni. Tehát | λ | = 0. A V +∪{ λ } halmazt a V feletti (összes) szavak halmazának hívjuk, s V *-al (ejtsd vécsillag) jelöljük. Speciálisan, ha valamely aV-re V = { a} azaz V egyelemű halmaz, s egyetlen eleme egy bizonyos a betű, akkor gyakran írunk { a } * helyett a *-ot, illetve { a}+ helyett a +-t. Valamely V *-beli p=a 1am és q=b 1bn (a 1,…,am ,b 1,…,bn  ∈ V) szavakat pontosan akkor tekintjük egyenlőknek, ha m = n és minden i = 1,…,n-re ai = bi . Ezt a tényt ki szokás úgy is fejezni, hogy V*-ban csak grafikus (betűről - betűre megegyező) egyenlőségek léteznek.

A V ábécé feletti szavak egy tetszőleges L halmazát a V ábécéből alkotott (formális) nyelvnek nevezzük, vagyis a V * halmaz részhalmazait V feletti formális nyelveknek, vagy röviden V feletti nyelveknek, vagy csak egyszerűen nyelveknek hívjuk. Valamely LV * nyelvet üresnek, végesnek vagy végtelennek hívunk ha az L (mint halmaz) üres, véges, illetve végtelen.

Azt a nyelvet, amelynek egyetlen szava sincs, üres nyelvnek nevezzük. Jelölés: ∅. Nem tévesztendő össze a { λ } nyelvvel, amely egyedül az üresszót tartalmazza.

Az így definiált nyelvfogalom túl általános, magában foglalja mind a mesterséges, mind a természetes (írott) nyelvek összességét. A kérdés viszont az, hogyan lehet ténylegesen megadni egy konkrét nyelvet. Az egyszerű tulajdonságokkal rendelkező nyelveket máris megadhatjuk a halmazok megadásának különböző módjai szerint. Legyen például a véges ábécénk mindössze két elemű: V={0,1}. Ekkor az

  • L 1 = { λ},

  • L 2 = { 1, 10, 0010, 111},

  • L 3 = { 1 i | i prím }

halmazok mindegyike egy-egy nyelv a fenti definíció értelmében. Szükségünk van azonban olyan eszközökre, amelyekkel a fentieknél lényegesen összetettebb nyelveket is definiálhatunk. Ebből a célból vezetjük be a generatív nyelvtan fogalmát.

Tehát a továbbiakban olyan nyelveket fogunk csak vizsgálni, melyek véges sok adat segítségével speciális módon, az úgynevezett generatív nyelvtanokkal megadhatók. Megjegyezzük azt is, hogy az általunk használt szófogalom nem esik egybe a természetes nyelvek szófogalmával, hisz egy természetes nyelvet úgy szokás tekinteni, mint az adott nyelv összes mondatainak halmazát. De tekinthetünk egy természetes nyelvet úgy is mint a nyelv összes véges hosszú szövegeinek halmazát. A szóközt és egyéb írásjeleket is felvéve az ábécébe, az általunk definiált szófogalom amellett, hogy magában foglalja a szokásos szófogalmat, magában foglalja mind a mondat fogalmát, mind pedig a tetszőleges véges hosszúságú szöveg fogalmát is.

2.2. példa - Szavak egyenlősége

Legyen V = { 1, 2, + }. Ekkor (V *- ban !) fennáll, hogy 1+1≠2, mivel az 1+1 szó nem egyezik meg "betűről - betűre", azaz grafikusan a 2 szóval. ★


2.3. példa - Véges és végtelen nyelvek

Legyen V = { 0,1,…,9}. A (magyar) történelmi dátumok { 1514, 1526, 1606, 1711, 1849, … } halmaza ekkor egy V feletti véges nyelv. A (tízes számrendszerbeli) páros számok halmaza egy V feletti végtelen nyelv. Temészetesen az üres halmaz is egy V feletti (üres) nyelv. Ugyancsak V feletti (véges) nyelv az egy elemű { λ } halmaz is. ★


A V * halmazon (és a V + halmazon is) szokás bevezetni egy (nagyon egyszerű tulajdonságú) műveletet, melyet szorzásnak nevezünk.

A p = a 1a m és q = b 1b n ( a 1, …, a m , b 1, …, b n V ) szavak szorzatán a pq = a 1 a 2 a m b 1 b 2 b n szót értjük. Két V *- beli (vagy két V +- beli) szót tehát úgy szorzunk össze, hogy e szavakat (megfelelő sorrendben) egymás mellé (után) írjuk. E műveletet konkatenációnak vagy összefűzésnek is szokás hívni. Természetesen ez a szorzásfajta általában nem kommutatív, azaz általában nem teljesül minden p, qV * párra a pq = qp egyenlőség. Amennyiben p = p 1p k ( ∈ V * k = 1,2,… ) továbbá p 1 = p 2 = … = p k = q úgy alkalmazni fogjuk a p = q k jelölést, s ezesetben p- t a q szó k-adik hatványának is nevezzük. Tehát a q szó k- adik hatványán az önmagával vett k- szoros konkatenációját értjük. Továbbá megállapodunk abban, hogy minden szó nulladik hatványa az üresszó (jelekben: ∀ qV * :q 0= λ.) Röviden úgy is mondhatjuk, hogy egy szó k- adik hatványa nem más mint k- szoros ismétlődése (beleértve a nullaszoros ismétlődést is).

2.4. példa - Szavak konkatenációja

Legyen ismét V = { ab}. Ekkor az abba V *- beli szó baba V *- beli szóval való szorzata abbababa lesz (ami persze nem egyezik meg a babaabba szóval. A szorzás tehát valóban, általában nem kommutatív). Igaz továbbá (definíció szerint), hogy baba=(ba)2. ★


2.5. példa - Szavak konkatenációja egyelemű ábécé felett

Legyen most V = { a}, azaz álljon ábécénk egyetlen betűből. Mutassuk meg hogy ebben a kivételes esetben a szorzás kommutatív. ★


A V *-ban ezen szorzás műveletre nézve a λ üresszó egységelem lesz, hisz minden pV *-ra pλ = λp = p (annak megfelelően, hogy ha egy szó - beleértve az üresszót is - elé vagy mögé nem írunk egyetlen betűt sem, azaz az üresszót "írjuk", akkor marad az eredeti szó). Nyilvánvaló továbbá, hogy minden p,q  ∈ V * párra | pq | = | p | + | q | .

Az előbbiekben definiált szorzás műveletével ellátott V * halmazt a V által generált egységelemes szabad félcsoportnak, más néven V feletti egységelemes szabad félcsoportnak, vagy röviden, V feletti szabad monoidnak hívjuk, s rá ugyancsak a V * jelölést használjuk.

Hasonlóan, a szorzás műveletével ellátott V + halmazt a V által generált szabad félcsoportnak, más néven V feletti szabad félcsoportnak hívjuk, s rá ugyancsak a V + jelölést használjuk. (V * tehát egyidejűleg jelöli az összes V feletti szavak halmazát és a V feletti szabad monoidot, míg V + az összes V feletti nem üres szavak halmazát és a V feletti szabad félcsoportot. Amennyiben tehát algebrai struktúraként tekintünk a V *-ra ( V +-ra), akkor a konkatenáció az alapértelmezett művelet az elemei közt.)

Nyilvánvaló, hogy V + zárt marad a szorzás, azaz az összefűzes műveletére, hisz két nem üresszót egymás után írva, azaz összefűzve, nem kaphatunk üresszót.

Legyen p és q tetszőleges két szó V *-ban. Azt mondjuk, hogy p kezdőszelete (prefixe) q-nak, ha van olyan rV *, hogy q = pr. Pontosabban, ha q = pr mellett | p | = k akkor a p szót a q szó k hosszúságú kezdőszeletének nevezzük (ekkor, ha 0 < k < | q | , akkor p a q valódi kezdőszelete). Hasonlóan, ha van olyan sV * szó, hogy q = sp, akkor azt mondjuk hogy p a q-nak végződése (szuffixe) és ha |p| = m akkor m hosszúságú végződésről beszélünk (ekkor ha pλ és pq akkor p valódi végződése a q-nak). Végül, a pV * szót a q  ∈ V * szó részszavának mondjuk, ha van olyan r, sV *, hogy q = rps. Amennyiben pqpλ, valódi rész-szóról beszélünk. Tehát, egy szó önmagától különböző nemüres kezdőszeleteit, végződéseit, illetve részszavait valódi kezdőszeletnek, valódi végződésnek, illetve valódi részszónak hívjuk.

Egy pV + szó utolsó betűjére használni fogjuk a ≫ p jelölést.

2.6. példa - Szó részszava

Legyen V = { a, b}, p = abbababa. Ekkor p-nek 4 hosszúságú kezdő szelete abba, 4 hosszúságú végződése pedig baba lesz. Ugyanekkor p-nek például a bab szó (valódi) rész-szava. Végül, ≫ p = a (abbababa utolsó betűje). ★