Főmenü megnyitása

A formális nyelv a matematika, a logika és az 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 szerint é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

DefinícióSzerkesztés

Legyen   véges halmaz, amelyet a továbbiakban ábécének nevezünk.

Készítsünk   elemeiből véges sorozatokat minden lehetséges módon. Jelölje   az egyelemű sorozatok halmazát (ezekből értelemszerűen annyi van, ahány jelből áll az ábécé),   a kételeműekét, és így tovább.   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   az ábécé elemeiből képzett véges sorozatok halmazát (ezt az   á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  ,   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   betűvel jelölni, és ha többet is használunk, indexszel megkülönböztetni őket (például  ,  ,  , stb.)

PéldákSzerkesztés

Legyen az ábécé  . Ekkor egy jelsorozat például  . Egy egyszerű nyelv lehet a fenti ábécé alapján például az, amely az összes olyan jelsorozatot tartalmazza, amelyekre igaz, hogy ugyanannyi   szimbólumból és   szimbólumból állnak.

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

  • Az üres halmaz és maga   is nyelvek. Triviális nyelvek.
  •   (ahol   az   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.

Formális nyelvek megadása, definiálásaSzerkesztés

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) 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.

Műveletek formális nyelvekkelSzerkesztés

Adott formális nyelvből vagy nyelvekből műveletekkel új nyelvek állíthatóak elő. Tegyük fel, hogy   és   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:

HalmazműveletekSzerkesztés

  • metszet –  közösrész képzés művelet az   és   nyelvre előállítja az összes olyan jelsorozatot, amelyek  -ben és  -ben is léteznek.
  • unió –  egyesítés művelet az   és   nyelvre előállítja az összes olyan jelsorozatot, amelyek vagy  -ben vagy  -ben léteznek.
  • komplementer –   – az   nyelvre előállítja az összes olyan jelsorozatot, amelyek az   nyelvben nem szerepelnek, de az   alaphalmazban igen.
  • különbség –  különbségképzés művelet az   és   nyelvekre előállítja az összes olyan jelsorozatot, amelyek  -ben léteznek,  -ben viszont nem.

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

Egyéb műveletekSzerkesztés

  • konkatenáció –  konkatenáció vagy összekapcsolás művelet előállítja az összes   formájú jelsorozatot, ahol   egy  -ből származó jelsorozat, és   a  -ből származó jelsorozat.
  • A right quotient különbségképzés művelet az   és   nyelvek között előállítja az összes olyan  -ben létező   jelsorozatot, amely jelsorozatok az   nyelvben   formában fordulnak elő (ahol   jelsorozat az   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   formában leírható jelsorozatot, ahol a   jelsorozat az   nyelvben létezik és  ). Meg kell jegyezni, hogy az   értékadás megengedett, tehát az   üres jelsorozat mindig része a   nyelvnek, minden   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 fordítottja művelet előállítja az összes   nyelvben létező jelsorozat fordítottját ( például az   jelsorozat fordítottja a   jelsorozat).
  • A shuffle, megkever művelet az   és az   nyelvek között előállítja az összes   formában leírható jelsorozatot, ahol   és a   jelsorozatok, amelyek az   nyelvben léteznek, és az előzőek szerinti értelemben össze vannak kapcsolva a   jelsorozatokkal, amelyek az   nyelvben léteznek.

A generatív nyelvekSzerkesztés

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.

Matematikai-nyelvészeti problémákSzerkesztés

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?

Lásd mégSzerkesztés

ForrásokSzerkesztés

További információkSzerkesztés