Formális nyelv
A Wikipédiából, a szabad lexikonbó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 (pl. 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. Ekkor formális nyelvnek nevezzük
minden 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őle alkotható jelsorozatok hossza is véges, egy nyelvhez végtelenül sok jelsorozat tartozhat (mivel a szavak hossza nincs korlátozva).
[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 Kleene star –
– a Kleene csillag 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 része az L1 nyelvnek. - A reverse –
– fordítottja művelet előállítja az összes L1 nyelvben létező jelsorozat fordítottját ( pl. 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.
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.
[szerkesztés] A formális nyelvek Chomsky féle hierarchiája (Chomsky nyelvosztályok)
A formális nyelvek egy osztályozási módja a Chomsky féle hierarchia, amely az őket generáló formális nyelvtanok hierarchiájára alapul:
| Típus | Nyelvtan | Nyelv | Minimális automata |
|---|---|---|---|
| 0. nyelvosztály | Korlátozás nélküli | Rekurzívan felsorolható | Turing-gép |
| 1. nyelvosztály | Környezet függő | Környezet függő | Korlátos, nem determinisztikus |
| 2. nyelvosztály | Környezet független | Környezet független | Pushdown |
| 3. nyelvosztály | Reguláris | Reguláris | Véges |


Based on work by