V matematice , informatice a lingvistice je formální jazyk sada slov . Abeceda formálního jazyka je sada symbolů, písmen nebo lexémů, které se používají ke konstrukci slov jazyka; často se předpokládá, že je tato abeceda hotová. Cílem teorie formálních jazyků je popsat formální jazyky.
Slova jsou sekvence prvků této abecedy; slova, která patří k určitému formálnímu jazyku, se někdy nazývají dobře vytvořená slova nebo dobře formulované vzorce . Formální jazyk je často definován formální gramatikou , jako jsou algebraické gramatiky, a analyzován automaty .
Teorie formálních jazyků studuje čistě syntaktické aspekty těchto jazyků, to znamená jejich formální vnitřní strukturu. Teorie jazyků vychází z lingvistiky jako prostředku porozumění syntaktickým zákonitostem přirozených jazyků :
Studium formálních jazyků zahrnuje všechny způsoby popisu a analýzy těchto jazyků, jako jsou formální gramatiky pro generování a automaty pro rozpoznávání, ale zajímá se také o strojové učení a překlad . V oblasti překladu se teorie jazyků vztahuje na překladače programovacích jazyků.
Dáme si množinu zvanou abeceda, jejíž prvky se nazývají písmena .
Tento zákon vnitřní kompozice je asociativní a připouští prázdné slovo pro neutrální prvek (což ospravedlňuje notaci ). V důsledku toho je sada stanovená tímto zákonem monoidem . Je to bezplatný monoid ve smyslu algebry.
Formální jazyk je soubor slov na konečných abeceda, to znamená, že část volné monoid na této abecedy.
Některé příklady formálních jazyků:
Formální jazyk lze určit různými způsoby. Hledá se konečná a explicitní metoda nebo mechanismus, který umožňuje vytvořit nebo analyzovat obecně nekonečný jazyk. Mezi tyto metody patří:
Typické otázky, které si klademe ohledně formálního jazyka, jsou následující:
Tyto otázky souvisejí s teorií vypočítatelnosti a složitosti .
Jazyky jsou seskupeny do jazykových rodin. Chomského hierarchie nám poskytuje čtyři typy gramatiky, přičemž každý typ gramatiky vytváří jazykovou rodinu.
Tyto jazykové sady jsou navzájem zahrnuty a jsou zde uvedeny od největší sady po nejmenší. Takže veškerý racionální jazyk je algebraický , což je samo o sobě kontextové , což je samo o sobě rekurzivně spočetné .
Mezi těmito 4 rodinami jazyků je možné si povšimnout rodin, které nejsou součástí Chomského hierarchie, ale které zůstávají pozoruhodné svými definicemi a vlastnostmi. Tyto deterministické bezkontextové jazyky jsou jazyky uznávané automaty deterministické stohu a jsou striktně zahrnuty v rodině algebraických jazyků. Tyto rekurzivní jazyky jsou jazyky uznávané Turing stroj, a jehož doplňkem je také rozpoznán Turing stroj. Proto jsou striktně zahrnuty v rekurzivně nespočetných jazycích .
K výrobě nových jazyků z daných jazyků lze použít několik operací. Předpokládejme, že L a M jsou jazyky na nějaké běžné abecedě.
Průsečík operací operací , sjednocení a doplňování jsou definovány jako pro jakoukoli sadu.
Zřetězení z L a M , bylo právě uvedeno , je množina slov tvaru xy , kde x je slovo L a tam je slovo M .
Podíl na levé části slova je soubor slov , například patří k . Kvocient vlevo se také nazývá zbytkový .
Podíl na pravé části slova je definován symetricky jako množina slov , například patří .
Kvocientu na levé straně a podíl na právo rozšířit na jazyky. Kvocient nalevo od jazyka , jak je uvedeno , je tedy sjednocení jazyků pro v .
Kleene hvězda z L je množina všiml, složený ze slov formuláře s a . Tato sada obsahuje slovo prázdné .
Reverzní z L , poznamenat, nebo obsahuje zrcadlové slova slova L , to znamená, že slova L číst zprava doleva.
Směs z L a M , označená L Ш M je množina slov, která mohou být zapsány , kde a jsou slova (případně prázdný) jako buď slovo L a buď slovem z M . Například Ű .
Aplikace je morphism nebo homomorphism si všechna slova o . Homomorfní obraz jazykového ON je množina
.Zneužíváním jazyka nazýváme inverzní morfismus inverzí morfismu. Inverzní morfismus z je označován funkce z v množině dílů z definovaný
.Obecně to není morfismus. Obraz by inverzním morfismu jednoho jazyka na je jazyk
.Morfismus nevymazává ani se nezvyšuje, nebo napodobováním angličtiny neobsahuje ε, pokud obraz dopisu nikdy není prázdným slovem. V tomto případě je délka obrazu slova větší nebo stejná jako délka slova.
Běžnou otázkou těchto operací je znát uzavírací vlastnosti každé jazykové rodiny pro každou z těchto operací, tj. Pokud jazyk, který je výsledkem operace, zůstává ve stejné rodině jazyků jako jazyky, z nichž pochází.
Racionální jazyky |
Deterministické algebraické jazyky |
Algebraické jazyky |
Kontextové jazyky |
Rekurzivní jazyky |
Rekurzivně vyčíslitelné jazyky |
|
---|---|---|---|---|---|---|
svaz | Zavřeno | Žádný plot | Zavřeno | Zavřeno | Zavřeno | Zavřeno |
Průsečík | Zavřeno | Žádný plot | Žádný plot | Zavřeno | Zavřeno | Zavřeno |
Komplementární | Zavřeno | Zavřeno | Žádný plot | Zavřeno | Zavřeno | Žádný plot |
Zřetězení | Zavřeno | Žádný plot | Zavřeno | Zavřeno | Zavřeno | Zavřeno |
Hvězda Kleene | Zavřeno | Žádný plot | Zavřeno | Zavřeno | Zavřeno | Zavřeno |
Zrcadlo | Zavřeno | Žádný plot | Zavřeno | Zavřeno | Zavřeno | Zavřeno |
Smíšený | Zavřeno | Žádný plot | Žádný plot | Žádný plot | Žádný plot | Žádný plot |
Morfismus | Zavřeno | Žádný plot | Zavřeno | Žádný plot | Žádný plot | Zavřeno |
Rostoucí morfismus | Zavřeno | Žádný plot | Zavřeno | Zavřeno | Zavřeno | Zavřeno |
Reverzní morfismus | Zavřeno | Zavřeno | Zavřeno | Zavřeno | Zavřeno | Zavřeno |