Formális nyelv
A Wikipédiából, a szabad enciklopédiából.
A formális nyelv a matematika, a logika és a informatika számára egy véges ábécéből generálható, véges hosszúságú szavak (például karakter stringek, jelsorozatok) halmaza, amelyekkel a formális nyelvek elmélete foglalkozik. (Más kontextusban, mint például jog vagy politika, a formális nyelv kifejezés alatt egy, a napi beszédtől eltérő, udvarias, megfontolt, körülíró jellegű, túlzottan modoros kifejezési módot értenek. Jelen cikkben a formális nyelvet a formális nyelvek elmélete szerinti értjük, és minden esetben szigorúan csak írott nyelvről beszélünk, ezért a jelsorozat elemei megjeleníthető, nyomtatható karakterek.)
Tartalomjegyzék |
[szerkesztés] Definíció
Legyen 
véges halmaz, amelyet a továbbiakban ábécének nevezünk. Jelölje 
az ábécé elemeiből képzett véges sorozatok halmazát (ezt az A ábécé feletti univerzumnak hívjuk). Ekkor formális nyelvnek nevezzük 
egy (nem feltétlenül valódi) részhalmazát. Szokásos még az 
á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 e, ε vagy a Λ 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 L betűvel jelölni, és ha többet is használunk, indexszel megkülönböztetni őket (például L1, L2, La, stb.)
[szerkesztés] Példák
Legyen az ábécé 
. Ekkor egy jelsorozat például ababba. Egy egyszerű nyelv lehet a fenti ábécé alapján például az, amely az összes olyan jelsorozatot tartalmaza, amelyekre igaz, hogy ugyanannyi a szimbólumból és b szimólumból állnak.
Néhány további példa formális nyelvekre:
- Az üres halmaz és maga A * is nyelvek. Triviális nyelvek.
(ahol an az 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.
[szerkesztés] Formális nyelvek megadása, definiálása
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
- 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) szabályos 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álsz adható, azok a kérdések, amelyekre IGEN a válasz – lásd döntési probléma.
[szerkesztés] Műveletek formális nyelvekkel
Adott formális nyelvből vagy nyelvekből műveletekkel új nyelvek állíthatóak elő. Tegyük fel, hogy L1 és L2 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:
[szerkesztés] Halmazműveletek
- metszet –
– közösrész képzés művelet az L1 és L2 nyelvre előállítja az összes olyan jelsorozatot, amelyek L1-ben és L2-ben is léteznek. - unió –
– egyesítés művelet az L1 és L2 nyelvre előállítja az összes olyan jelsorozatot, amelyek vagy L1-ben vagy L2-ben léteznek. - komplementer –
– az L1 nyelvre előállítja az összes olyan jelsorozatot, amelyek az L1 nyelvben nem szerepelnek, de az A * alaphalmazban igen. - különbség –
– különbségképzés művelet az L1 és L2 nyelvekre előállítja az összes olyan jelsorozatot, amelyek L1-ben léteznek L2-ben viszont nem.
A formális nyelvek speciális halmazok, így speciális műveletek is értelmezhetőek rajtuk:
[szerkesztés] Egyéb műveletek
- konkatenáció – L1L2 – konkatenáció vagy összekapcsolás művelet előllítja az összes vw formájú jelsorozatot, ahol v egy L1-ből származó jelsorozat, és w a L2-ből származó jelsorozat.
- A right quotient – L1 / L2 – különbségképzés művelet az L1 és L2 nyelvek között előállítja az összes olyan L2-ben létező w jelsorozatot, amely jelsorozatok az L1 nyelvben vw formában fordulnak elő (ahol v jelsorozat az L1 nyelvben létezik).
- A tranzitív lezárt (lezárt, lezárás, angolul Kleene star, Kleene csillag) –
– a tranzitív lezárt művelet előállítja az összes w1w2...wn formában leírható jelsorozatot, ahol a wi jelsorozat az L1 nyelvben létezik és 
). Meg kell jegyezni, hogy az n = 0 értékadás megengedett, tehát az ε üres jelsorozat mindig része a nyelvnek, minden L1 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 az 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 –
– fordítottja művelet előállítja az összes L1 nyelvben létező jelsorozat fordítottját ( például az ababba jelsorozat fordítottja a abbaba jelsorozat). - A shuffle, megkever művelet az L1 és az L2 nyelvek között előállítja az összes v1w1v2w2...vnwn formában leírható jelsorozatot, ahol
és a v1,...,vn jelsorozatok, amelyek az L1 nyelvben léteznek, és az előzőek szerinti értelemben össze vannak kapcsolva a w1,...,wn jelsorozatokkal, amelyek az L2 nyelvben léteznek.
[szerkesztés] A generatív nyelvek
Bővebben: Formális nyelvtanA 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.
[szerkesztés] Nyelvészeti problémák
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ági elméletnek és komplexitási elmé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?
[szerkesztés] Lásd még
[szerkesztés] Források
- 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
