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 A = \left \{ a_1, a_2, \dots, a_n \right \} véges halmaz, amelyet a továbbiakban ábécének nevezünk. Jelölje A^* = A^{0} \cup A^{1} \cup A^{2} \cup \dots az ábécé elemeiből képzett véges sorozatok halmazát. Ekkor formális nyelvnek nevezzük A^{*}\, minden részhalmazát. Szokásos még az 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 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é A=\left \{ a , b \right \}. 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.
  • L_1 = \left \{ a^{n} : n \in \mathbb{N} \right \} (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 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) 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 – L_1 \cap L_2kö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ó – L_1 \cup L_2egyesí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 – \bar{L_{1}} – 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 – L_1 \setminus L_2kü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ó – L1L2konkatená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 quotientL1 / L2kü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 starL_{1}^{*} – 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 n \ge 0). Meg kell jegyezni, hogy az n = 0 értékadás megengedett, tehát az ε üres jelsorozat része az L1 nyelvnek.
  • A reverseL_{1}^{R}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 n \ge 1 é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