Formális nyelv

A Wikipédiából, a szabad lexikonból.

Ezt a szócikket át kellene olvasni, ellenőrizni a szövegét, tartalmát. További részleteket a cikk vitalapján találhatsz.

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. Meg kell jegyezni, hogy több területen (tudomány, jog, nyelvészet stb.), a formális nyelv alatt egy, a napi beszédtől eltérő, udvarias, megfontolt, körülíró jellegű, túlzottan modoros kifejezési módot értenek.

A következőkben 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.

Legyen egy ábécé a \left \{ a , b \right \}, és az ábécé alapján létrehozott jelsorozat legyen például ababba.

Egy tipikus 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.

Az üres szó (ami nem más, mint egy nulla hosszúságú jelsorozat) megengedett és gyakran az e, ε vagy a Λ jelöli. 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).

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

  • a a,b alapján generált összes szó halmaza
  • a \left \{ a^{n}\right\} művelettel létrehozott szavak halmaza, (ahol n prím szám és 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 .

Egy formális nyelv nagyon sok lehetséges módon meghatározható, többek között:

  • Jelsorozatok létrehozása valamilyen formális nyelvtan alapján (lásd még Chomsky féle hierarchia);
  • Jelsorozatok létrehozása szabályos kifejezések segítségével;
  • 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.

Néhány művelettel új nyelv állítható elő adott nyelvből vagy nyelvekből. Tegyük fel, hogy L1 és L2 közös ábécén értelmezett nyelvek.

  • A concatenationL1L2konkatená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.
  • Az intersectionL_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.
  • A unionL_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.
  • A complement, komplementer képzés vagy kiegészítő képzés művelet az L1 nyelvre előállítja az összes olyan jelsorozatot, amelyek az L1 nyelvben nem léteznek.
  • 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

Típus Nyelvtan Nyelv Minimális automata
Type-0 Korlátozás nélküli Rekurzívan felsorolható Turing-gép
Type-1 Környezet függő Környezet függő Korlátos, nem determinisztikus
Type-2 Környezet független Környezet független Pushdown
Type-3 Szabályos Szabályos Véges