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. 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
, é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
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 concatenation — 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.
- Az intersection —
— 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. - A union —
— 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. - 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 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
| 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 |


Based on work by GaborLajos és