From Wikipedia, the free encyclopedia
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 karakterstringek, 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.)
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.)
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:
Egy formális nyelv nagyon sok lehetséges módon meghatározható, többek között:
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:
A formális nyelvek speciális halmazok, így speciális műveletek is értelmezhetőek rajtuk:
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:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.