Formális nyelv

Legyen ${\displaystyle A=\left\{a_{1},a_{2},\dots ,a_{n}\right\}}$  véges halmaz, amelyet a továbbiakban ábécének nevezünk.

Készítsünk ${\displaystyle A}$  elemeiből véges sorozatokat minden lehetséges módon. Jelölje ${\displaystyle A^{1}}$  az egyelemű sorozatok halmazát (ezekből értelemszerűen annyi van, ahány jelből áll az ábécé), ${\displaystyle A^{2}}$  a kételeműekét, és így tovább. ${\displaystyle A^{0}}$  jelenti az üres sorozatok halmazát (ez megint csak könnyen beláthatóan egyelemű). A hatványjelölés a halmaz önmagával vett Descartes-szorzataira utal.

Jelölje ${\displaystyle A^{*}=A^{0}\cup A^{1}\cup A^{2}\cup \dots }$  az ábécé elemeiből képzett véges sorozatok halmazát (ezt az ${\displaystyle A}$  ábécé feletti univerzumnak hívjuk). Ekkor formális nyelvnek nevezzük ${\displaystyle A^{*}\,}$  egy (nem feltétlenül valódi) részhalmazát. Szokásos még az ${\displaystyle A\,}$  ábécé feletti formális nyelv megnevezés is.

Észrevehető, hogy a definíció megengedi az üres szót is (ami nem más, mint egy nulla hosszúságú jelsorozat), és gyakran az ${\displaystyle e}$ , ${\displaystyle \epsilon }$  vagy a ${\displaystyle \Lambda }$  szimbólumokkal jelölik. Bár véges halmaz az ábécé, és a belőlük képzett jelsorozatok (szavak) hossza is véges (bár nem korlátos), egy nyelvhez mégis akár megszámlálhatóan végtelenül sok jelsorozat is tartozhat (mivel a szavak száma nincs korlátozva, akár a teljes univerzumot is vehetjük!). A formális nyelvek száma kontinuum számosságú (mivel az univerzum hatványhalmazát képezve megkapjuk az összes formális nyelv halmazát; és nyilván az univerzum megszámlálhatóan végtelen számosságú, mivel elemei felsorolhatóak).

Kitüntetett nyelvek az univerzum, a csak az üres jelsorozatot tartalmazó nyelv, és az egyetlen jelsorozatot sem tartalmazó nyelv.

Az egyes nyelveket szokás ${\displaystyle L}$  betűvel jelölni, és ha többet is használunk, indexszel megkülönböztetni őket (például ${\displaystyle L_{1}}$ , ${\displaystyle L_{2}}$ , ${\displaystyle L_{a}}$ , stb.)

Legyen az ábécé ${\displaystyle A=\left\{a,b\right\}}$ . Ekkor egy jelsorozat például ${\displaystyle ababba}$ . Egy egyszerű nyelv lehet a fenti ábécé alapján például az, amely az összes olyan jelsorozatot tartalmazza, amelyekre igaz, hogy ugyanannyi ${\displaystyle a}$  szimbólumból és ${\displaystyle b}$  szimbólumból állnak.

Néhány további példa formális nyelvekre:

• Az üres halmaz és maga ${\displaystyle A^{*}}$  is nyelvek. Triviális nyelvek.
• ${\displaystyle L_{1}=\left\{a^{n}:n\in \mathbb {N} \right\}}$  (ahol ${\displaystyle a^{n}}$  az ${\displaystyle a}$  n-szeri ismétlését jelenti)
• egy adott programozási nyelven szintaktikailag helyes programok halmaza, vagy
• egy bizonyos Turing-gépet megállító bemeneti jelek halmaza.

Egy formális nyelv nagyon sok lehetséges módon meghatározható, többek között:

• A jelsorozatok felsorolásával. Például ${\displaystyle L:=\left\{abba,baba,bab\right\}}$ 
• A jelsorozatok létrehozása (generálása) valamilyen formális nyelvtan alapján (lásd még Chomsky-féle hierarchia);
• A jelsorozatok létrehozása (generálása) reguláris kifejezések segítségével;
• A tartalmazott jelsorozatok elfogadása valamilyen automata használatával, például Turing-gép vagy véges állapotú automata;
• Azon kérdések halmazából, amelyekre IGEN/NEM válasz adható, azok a kérdések, amelyekre IGEN a válasz – lásd döntési probléma.

Adott formális nyelvből vagy nyelvekből műveletekkel új nyelvek állíthatóak elő. Tegyük fel, hogy ${\displaystyle L_{1}}$  és ${\displaystyle L_{2}}$  közös ábécén értelmezett nyelvek. A formális nyelvek halmazok, tehát a halmazműveletek minden további nélkül alkalmazhatóak rájuk:

• metszet – ${\displaystyle L_{1}\cap L_{2}}$  – közösrész képzés művelet az ${\displaystyle L_{1}}$  és ${\displaystyle L_{2}}$  nyelvre előállítja az összes olyan jelsorozatot, amelyek ${\displaystyle L_{1}}$ -ben és ${\displaystyle L_{2}}$ -ben is léteznek.
• unió – ${\displaystyle L_{1}\cup L_{2}}$  – egyesítés művelet az ${\displaystyle L_{1}}$  és ${\displaystyle L_{2}}$  nyelvre előállítja az összes olyan jelsorozatot, amelyek vagy ${\displaystyle L_{1}}$ -ben vagy ${\displaystyle L_{2}}$ -ben léteznek.
• komplementer – ${\displaystyle {\bar {L_{1}}}}$  – az ${\displaystyle L_{1}}$  nyelvre előállítja az összes olyan jelsorozatot, amelyek az ${\displaystyle L_{1}}$  nyelvben nem szerepelnek, de az ${\displaystyle A^{*}}$  alaphalmazban igen.
• különbség – ${\displaystyle L_{1}\setminus L_{2}}$  – különbségképzés művelet az ${\displaystyle L_{1}}$  és ${\displaystyle L_{2}}$  nyelvekre előállítja az összes olyan jelsorozatot, amelyek ${\displaystyle L_{1}}$ -ben léteznek, ${\displaystyle L_{2}}$ -ben viszont nem.

A formális nyelvek speciális halmazok, így speciális műveletek is értelmezhetőek rajtuk:

• konkatenáció – ${\displaystyle L_{1}L_{2}}$  – konkatenáció vagy összekapcsolás művelet előállítja az összes ${\displaystyle vw}$  formájú jelsorozatot, ahol ${\displaystyle v}$  egy ${\displaystyle L_{1}}$ -ből származó jelsorozat, és ${\displaystyle w}$  a ${\displaystyle L_{2}}$ -ből származó jelsorozat.
• A right quotient – ${\displaystyle L_{1}/L_{2}}$  – különbségképzés művelet az ${\displaystyle L_{1}}$  és ${\displaystyle L_{2}}$  nyelvek között előállítja az összes olyan ${\displaystyle L_{2}}$ -ben létező ${\displaystyle w}$  jelsorozatot, amely jelsorozatok az ${\displaystyle L_{1}}$  nyelvben ${\displaystyle vw}$  formában fordulnak elő (ahol ${\displaystyle v}$  jelsorozat az ${\displaystyle L_{1}}$  nyelvben létezik).
• A tranzitív lezárt (lezárt, lezárás, angolul Kleene star, Kleene csillag) – ${\displaystyle L_{1}^{*}}$  – a tranzitív lezárt művelet előállítja az összes ${\displaystyle w_{1}w_{2}...w_{n}}$  formában leírható jelsorozatot, ahol a ${\displaystyle w_{i}}$  jelsorozat az ${\displaystyle L_{1}}$  nyelvben létezik és ${\displaystyle n\geq 0}$ ). Meg kell jegyezni, hogy az ${\displaystyle n=0}$  értékadás megengedett, tehát az ${\displaystyle \epsilon }$  üres jelsorozat mindig része a ${\displaystyle L_{1}^{*}}$  nyelvnek, minden ${\displaystyle L_{1}}$  nyelvre! (Ha az eredeti nyelv nem is tartalmazta az üres jelsorozatot, a tranzitív lezártja akkor is tartalmazni fogja!) A legalább egy betűt (karaktert) tartalmazó nyelvek tranzitív lezártja végtelen számosságú; az elnevezés onnan származik, hogy a tranzitív lezárt az összes olyan elemet tartalmazza, ami az eredeti nyelv szavaiból kiindulva konkatenációk tetszőleges egymás után alkalmazásával megkapható (lezárt, mert ez a „legnagyobb” ilyen halmaz, elemeinek konkatenációjával már nem bővíthető).
• A reverse – ${\displaystyle L_{1}^{R}}$  – fordítottja művelet előállítja az összes ${\displaystyle L_{1}}$  nyelvben létező jelsorozat fordítottját ( például az ${\displaystyle ababba}$  jelsorozat fordítottja a ${\displaystyle abbaba}$  jelsorozat).
• A shuffle, megkever művelet az ${\displaystyle L_{1}}$  és az ${\displaystyle L_{2}}$  nyelvek között előállítja az összes ${\displaystyle v_{1}w_{1}v_{2}w_{2}...v_{n}w_{n}}$  formában leírható jelsorozatot, ahol ${\displaystyle n\geq 1}$  és a ${\displaystyle v_{1},...,v_{n}}$  jelsorozatok, amelyek az ${\displaystyle L_{1}}$  nyelvben léteznek, és az előzőek szerinti értelemben össze vannak kapcsolva a ${\displaystyle w_{1},...,w_{n}}$  jelsorozatokkal, amelyek az ${\displaystyle L_{2}}$  nyelvben léteznek.

Bővebben: Formális nyelvtan

A formális nyelvek definíciója (hogy minden formális nyelv egy univerzum részhalmaza) nyilván általános, de praktikus értelemben használhatatlan definíció (hiszen például egy végtelen számosságú nyelvet nem tudunk kezelni így, nem tudjuk felsorolni az elemeit). A gyakorlati problémák szempontjából fontosabb a generatív nyelvek osztálya; generatív nyelvek azok a nyelvek, amelyekre igaz, hogy van olyan nyelvtan (más néven grammatika), ami éppen az ő elemeiket generálja.

A formális nyelvekkel kapcsolatosan gyakran felmerülő kérdés „milyen nehéz eldönteni egy adott szóról, hogy egy adott nyelvhez tartozik-e?” Ez az alapja a kiszámíthatóságelméletnek és bonyolultságelméletnek.

További fontos, generatív nyelvekkel kapcsolatos problémák:

• Egy nyelvtan a teljes univerzumot generálja-e?
• Két nyelvtan ugyanazt a nyelvet generálja-e?
• Egy nyelvtan által generált nyelv tartalmazza-e egy másik nyelvtan által generált nyelv minden szavát?

• Elsőrendű nyelv

• Bach, Iván. Formális nyelvek: Egyetemi tankönyv. Budapest: Typotex (2002). ISBN 963 9132 92 6 
• Csirmaz, László: Matematikai logika egyetemi jegyzet, ELTE Bp., 1994 (Postscript változat)
• Szeredi – Lukácsy – Benkő: A szemantikus világháló elmélete és gyakorlata. Typotex Kiadó, 2005. ISBN 963-9548-48-0

• Alice és Bob – 6. rész: Alice és Bob a kiszámíthatóság határán
• Alice és Bob – 7. rész: Alice és Bob egymillió dolláros kérdése
• Alice és Bob – 8. rész: Alice és Bob biztonsága