Formális nyelvek

A formális nyelv a mindennapi életből ismert nyelv fogalmának egyfajta általánosítása.

Alapfogalmak

A formális nyelvet kezdetben úgy képzelhetjük el, mint egy hétköznapi nyelvet, például a magyart. Miből áll egy ilyen nyelv? Szavakból, amelyeket aztán mondatokká fűzünk össze. A mondatok most nem érdekelnek minket, csak a szavak. Miből állnak a szavak? Az ábécé betűiből. Az ábécével kezdjük tehát.

Az ábécé tetszőleges nem üres halmaz. Az ábécé elemeit szimbólumoknak nevezzük. Ha a magyar nyelvről van szó, akkor ez a megszokott magyar ábécé lesz, amely tartalmazza a kis- és nagybetűket, valamint az ékezetes betűket. Ha nem a magyar nyelvet, hanem például a számokat szeretnénk leírni, akkor az ábécénkben mind a tíz számjegy szerepelne. Az ábécét gyakran a Σ szimbólummal jelöljük.

Szónak, más néven sztringnek egy Σ ábécé szimbólumaiból álló véges sorozatot nevezünk. Ha például a Σ= {a,b,c,d,e,…, z} ábécénk van, akkor szó például a „szia” vagy a „kutya” sorozat, de már nem szó a „tükör” (nincs benne ü és ö betű), a „Pista” (nincs benne nagy P betű) és a „jo napot” (nincs benne szóköz). A szó hosszán a szót alkotó szimbólumok számát értjük.

Szavak összefűzése: ha adott két szó, a = a₁a₂… a_n és b = b₁b₂… b_m, akkor a szavak összefűzésével az ab = a₁a₂… a_nb₁b₂… b_m szó jön létre. Példa: a „szia” és a „kutya” szó összefűzésével a „sziakutya” szó keletkezik. Az összefűzést vagy kis körrel jelöljük, azaz a ∘ b, vagy sehogy sem jelöljük, és a szavakat egyszerűen egymás mellé írjuk külön összefűzési jel nélkül.

Az üres szót ε jelöli, és ez a nulla hosszúságú szó. Ha az a = a₁… a_n szót összefűzzük az ε üres szóval, visszakapjuk az a szót. Vagyis igaz, hogy a ∘ ε = a.

A Σ ábécé lezárása az összes olyan szó halmaza, amelyet a Σ ábécéből létre tudunk hozni, az üres szót is beleértve. A lezárást Σ^∗ jelöli. Ha a Σ= {0, 1} bináris ábécénk van, akkor

$${\mathrm{\Sigma }}^{\ast }=\{\epsilon ,0,1,00,01,10,11,000,001,\dots \}$$

Néha használjuk még az ábécé pozitív lezárását is, ami megint az összes szó, amelyet az ábécéből össze tudunk állítani, az üres szó kivételével. A pozitív lezárást Σ⁺ jelöli, és Σ⁺ = Σ^∗ ∖ {ε}.

Példák ábécékre

• Térjünk vissza a magyar nyelves példához. Minden magyar szót megtalálunk annak az ábécének a lezárásában, amely tartalmazza a kis- és nagybetűket és az ékezetes változatokat (és talán még a kötőjelet „-”). Ha ehhez az ábécéhez hozzávesszük még a szóközt és az írásjeleket (vessző, pont, felkiáltójel, kérdőjel, …), akkor a lezárásban megkapjuk az összes mondatot, amelyet magyarul létre tudunk hozni. Természetesen ennek a lezárásnak része lesz az olyan „sadflsf kasdf kagrjewikjáűőker kf fkjbsjbgvbadfgsa!!!:??: ::!?:?:sdf” típusú mondat is.

• Ha az ábécénk az összes számjegyet tartalmazza, Σ= {0, 1, …, 9}, akkor a lezárásban ott lesz az összes pozitív egész szám – és még néhány további is. Lesznek benne ugyanis nullával kezdődő számok, pl. 00054, vagy maga a nulla, és ott lesz még az üres szó is, ami természetesen egyáltalán nem szám.

• Az ábécé nem lehet üres, ezért a legkisebb ábécének is legalább egy szimbóluma van. Például a Σ= {!} ábécé esetén a Σ^∗ = {ε, !, !!, !!!, !!!!, …} lezárást kapnánk, vagyis szavak halmazát, ahol minden n ∈ ℕ számhoz van a lezárásban egy n felkiáltójelből álló szó, és más szó nincs a lezárásban.

• Legyen Σ= {qw,c}. Ez egy nagyon különös ábécé, mert tartalmazza a qw szót. Ezt a jelölést általában nem használjuk, mert zavaros és furcsa, de elképzelhetjük úgy, hogy a „q” és a „w” betűt összeragasztjuk, és együtt egyetlen jelet alkotnak. Ekkor a „qw” szót egyetlen „qw” szimbólumnak láthatjuk. Ha ebből a szimbólumból létrehoznánk a „qwcqw” szót, akkor ennek a szónak a hossza három lenne – a „qw”, a „c” és a „qw” szimbólumból állna. Az ilyen ábécékkel nem találkozunk túl gyakran, de vannak helyzetek, amikor szükségünk van olyan szimbólumokra, amelyek több szimbólumból állnak.

Formális nyelv

A Σ ábécé feletti (formális) nyelv a Σ^∗ tetszőleges részhalmaza. A Σ ábécé feletti L nyelvre tehát igaz, hogy L ⊆ Σ^∗. Példák nyelvekre:

• Az előző részben definiáltuk a Σ= {0, 1, …, 9} számjegyábécét. A lezárás az összes olyan szó, amely csak számjegyekből áll. Ha hozzáadjuk azt a szabályt, hogy a szó nem kezdődhet nullával, és nem lehet üres, megkapjuk a pozitív egész számok halmazát, ℕ⁺. Fennáll az ℕ⁺ ⊆ Σ^∗ reláció, tehát ℕ⁺ nyelv a Σ ábécé felett.

• Az előbbi számjegyhalmazhoz hozzávehetjük még a mínusz „-” jelet, így Σ= {0, 1, …, 9, −}. A lezárás az összes olyan szó, amely számjegyekből vagy mínuszjelből áll. Ez viszont azt jelenti, hogy a lezárásban olyan szavak is vannak, mint a „12-84-”, az „1-5-8” vagy a „-”. Az egész számok ℤ nyelvét úgy hozzuk létre, hogy három szabályt adunk hozzá:

  • A mínuszjel a szóban egyáltalán nem fordul elő, vagy a szó elején áll.
  • A szó első számjegye nem lehet nulla, kivéve a „0” szót.
  • Minden szónak legalább egy számjegyet tartalmaznia kell.

  Ez a halmaz az egész számok halmazát írja le, és a Σ^∗ halmaz részhalmaza – tehát nyelv a Σ ábécé felett.

• Legyen Σ= {0, 1}. A lezárás tehát az összes olyan szó, amely nullákból és egyesekből áll. Az L nyelvet e fölött az ábécé fölött definiálhatjuk például úgy, mint az összes olyan szó halmazát, amelyben pontosan három egyes van. Lehetünk kreatívabbak is, és mondhatjuk, hogy az L nyelv azoknak a szavaknak a halmaza, amelyek érvényes docx fájlformátumot képviselnek (az, ami a Wordből kijön).

• Maradjunk a Σ= {0, 1} bináris ábécénél. Bármely karaktersorozat (a billentyűzeten található szokásos karakterekből) átalakítható bináris alakba, vagyis nullákba és egyesekbe, és vissza is, például az ASCII-tábla segítségével (vagy pontosabban: az ASCII-tábla a karaktereket számokká alakítja, a tízes számrendszerbeli számokat pedig át lehet váltani kettes számrendszerbe). Így definiálhatjuk az összes olyan szó nyelvét, amely érvényes e-mail-címnek felel meg, és ez még mindig a bináris ábécé feletti nyelv lesz.

Nyelvek összefűzése: nyelveket is összefűzhetünk. A definíció hasonló lesz, mint a halmazok Descartes-szorzatánál. Legyen két nyelvünk, L₁ és L₂. Az összefűzésükkel, L₁ ∘ L₂-vel, egy új nyelvet kapunk, amelyet így definiálunk:

$$L_1\circ L_2=\{w_1\circ w_2|w_1\in L_1,w_2\in L_2\}$$

Vagyis vesszük az L₁ nyelv összes szavát, és összefűzzük őket az L₂ nyelv összes szavával. Példa: legyen

$$\begin{array}{rcl}{L}_1& =& \{0,1\}\\ L_2& =& \{a,b,szia\}\end{array}$$

Ekkor:

$$\begin{array}{rcl}{L}_1\circ L_2& =& \{0a,0b,0szia,1a,1b,1szia\}\\ L_2\circ L_1& =& \{a0,a1,b0,b1,szia0,szia1\}\\ L_1\circ L_1& =& \{00,01,10,11\}\end{array}$$

Eddig a nyelvek leírására a hétköznapi nyelvet használtuk, vagyis egyszerűen szavakkal írtuk le, hogyan nézzen ki a nyelv. Ez viszont nagyon körülményes, ezért bevezetünk egy formálisabb módot is a nyelvek definiálására. Az első ilyen a nyelvtan.