A matematikában , az informatikában és a nyelvészetben a hivatalos nyelv a szavak összessége . A hivatalos nyelv ábécéje a szimbólumok, betűk vagy lexémák összessége, amelyeket a nyelv szavainak összeállításához használnak; gyakran feltételezik, hogy ez az ábécé elkészült. A formális nyelvelmélet célja a formális nyelvek leírása.
A szavak az ábécé elemeinek szekvenciái; egy bizonyos formális nyelvhez tartozó szavakat néha jól formált szavaknak vagy jól formált formuláknak nevezzük . A hivatalos nyelvet gyakran egy hivatalos nyelvtan határozza meg , például algebrai nyelvtan, és automaták elemzik .
A formális nyelvek elmélete az ilyen nyelvek pusztán szintaktikai vonatkozásait tanulmányozza , vagyis formális belső szerkezetüket. A nyelvelmélet a nyelvészetből ered , mint a természetes nyelvek szintaktikai törvényszerűségének megértésének eszköze :
A formális nyelvek tanulmányozása magában foglalja e nyelvek leírásának és elemzésének minden eszközét, például a formális nyelvtanokat a generáláshoz és az automatákat a felismeréshez, de érdekli a gépi tanulás és a fordítás is . A fordítás területén a nyelvelmélet a programnyelv- fordítókra vonatkozik .
Adunk magunknak egy halmazt , úgynevezett ábécét, amelynek elemeit betűknek nevezzük .
Ez a belső összetétel törvénye asszociatív, és a semleges elem üres szavát ismeri el (ami igazolja a jelölést ). Következésképpen az e törvény által biztosított halmaz monoid . Az algebra értelmében szabad monoid .
A hivatalos nyelv a véges ábécé szavainak halmaza, vagyis ezen az ábécén található szabad monoid része .
Néhány példa a hivatalos nyelvekre:
A hivatalos nyelvet különböző eszközökkel lehet meghatározni. Olyan véges és explicit módszer vagy mechanizmus keresendő, amely lehetővé teszi egy általában végtelen nyelv előállítását vagy elemzését. Ezen módszerek között vannak:
Tipikus kérdések, amelyeket felteszünk magunknak egy hivatalos nyelvvel kapcsolatban, a következők:
Ezek a kérdések összefüggenek a kiszámíthatóság és a komplexitás elméletével .
A nyelvek nyelvcsaládokba vannak csoportosítva. A Chomsky Hierarchia négyféle nyelvtant ad nekünk, mindegyik nyelvtani típus generál egy nyelvcsaládot.
Ezek a nyelvkészletek mind szerepelnek egymás között, és itt vannak a legnagyobb halmaztól a legkisebbig. Tehát minden racionális nyelve van algebrai , amely maga is a kontextus , amely maga is rekurzívan felsorolható .
E négy nyelvcsalád között meg lehet jegyezni azokat a családokat, amelyek nem részei a Chomsky-hierarchiának, de figyelemre méltóak maradnak meghatározásaik és tulajdonságaik révén. A determinisztikus kontextustól mentes nyelvek azok a nyelvek, amelyeket az automaták determinisztikus vereme felismer , és szigorúan az algebrai nyelvek családjába tartoznak. A rekurzív nyelvek azok a nyelvek, amelyeket egy Turing-gép felismer, és amelyek kiegészítését egy Turing-gép is felismeri. Ezért szigorúan szerepelnek rekurzívan megszámlálható nyelveken .
Számos művelettel lehet új nyelveket készíteni adott nyelvekből. Tegyük fel, hogy L és M valamilyen általános ábécé nyelvei.
A halmaz műveleteinek metszéspontja , egyesítése és kiegészítése minden halmazhoz hasonlóan meg van határozva.
A összefűzése a L és M , csak megjegyezte, a szavak halmazának az űrlap xy , ahol x egy szót L és ott egy szót M .
A hányados balra az egy szó a szavak halmazát , például tartozik . A baloldali hányadost reziduálisnak is nevezzük .
A hányados a jogot a szó definíciója szimmetrikusan azon szavak halmaza , például tartozik .
A bal és a jobb oldali hányados kiterjed a nyelvekre is. Tehát a nyelv által balra levő hányados, amelyet megjegyeztek , a nyelvek egyesülése az in nyelven .
A Kleene csillag az L halmaza észre tagjai szavak formájában a és . Ez a készlet az üres szót tartalmazza .
A fordított a L , megjegyezte , illetve tartalmazza a tükör szó szavai L , azaz a szavak L jobbról balra.
A keveréket a L és M , jele L Ш M jelentése a beállított szavak lehet írni , ahol a és a szavak (esetleg üres), mint akár egy szót L és akár egy szót M . Például Ш .
Egy alkalmazás egy morfizmus vagy homomorfizmus si minden szó az . A homomorf kép egy nyelvet a halmaza
.A nyelvvel való visszaélés révén az inverz morfizmust a morfizmus inverzének nevezzük . A inverz morfizmus az a jelölésük funkciója az a készlet részei által meghatározott
.Általában nem morfizmus. A kép egy inverz morfizmus egy nyelv a az a nyelv
.A morfizmus nem törlődik vagy növekszik, vagy az angol utánzásával ε-mentes, ha a betű képe soha nem az üres szó. Ebben az esetben a szó képének hossza nagyobb vagy egyenlő, mint a szóé.
Ezeknek a műveleteknek a közös kérdése az egyes nyelvcsaládok záró tulajdonságainak ismerete ezeknél a műveleteknél, vagyis ha a művelet eredményeként kapott nyelv ugyanazon nyelvcsaládban marad, mint azok a nyelvek, amelyekből származik.
Racionális nyelvek |
Determinisztikus algebrai nyelvek |
Algebrai nyelvek |
Kontextus szerinti nyelvek |
Rekurzív nyelvek |
Rekurzívan megszámlálható nyelvek |
|
---|---|---|---|---|---|---|
Unió | Zárva | Nincs kerítés | Zárva | Zárva | Zárva | Zárva |
Útkereszteződés | Zárva | Nincs kerítés | Nincs kerítés | Zárva | Zárva | Zárva |
Kiegészítő | Zárva | Zárva | Nincs kerítés | Zárva | Zárva | Nincs kerítés |
Összefűzés | Zárva | Nincs kerítés | Zárva | Zárva | Zárva | Zárva |
Kleene-csillag | Zárva | Nincs kerítés | Zárva | Zárva | Zárva | Zárva |
Tükör | Zárva | Nincs kerítés | Zárva | Zárva | Zárva | Zárva |
Vegyes | Zárva | Nincs kerítés | Nincs kerítés | Nincs kerítés | Nincs kerítés | Nincs kerítés |
Morfizmus | Zárva | Nincs kerítés | Zárva | Nincs kerítés | Nincs kerítés | Zárva |
Növekvő morfizmus | Zárva | Nincs kerítés | Zárva | Zárva | Zárva | Zárva |
Fordított morfizmus | Zárva | Zárva | Zárva | Zárva | Zárva | Zárva |