Formální jazyk - Formal language

Struktura syntakticky dobře formované, i když nesmyslné, anglické věty „Bezbarvé zelené myšlenky zuřivě spí“ ( historický příklad z Chomského 1957).

V logice , matematice , informatice a lingvistice se formální jazyk skládá ze slov, jejichž písmena jsou převzata z abecedy a jsou dobře formována podle konkrétního souboru pravidel.

Abeceda formálního jazyka se skládá ze symbolů, písmen, nebo tokeny, které CONCATENATE do řetězce jazyka. Každý řetězec zřetězený ze symbolů této abecedy se nazývá slovo a slovům, která patří do určitého formálního jazyka, se někdy říká dobře utvořená slova nebo dobře formulované vzorce . Formální jazyk je často definován pomocí formální gramatiky , jako je běžná gramatika nebo bezkontextová gramatika , která se skládá z pravidel její formace .

Oblast formální teorie jazyka studuje především čistě syntaktické aspekty takových jazyků - tedy jejich vnitřní strukturální vzorce. Formální teorie jazyků vznikla z lingvistiky jako způsobu porozumění syntaktickým zákonitostem přirozených jazyků . V informatice se formální jazyky používají mimo jiné jako základ pro definování gramatiky programovacích jazyků a formalizovaných verzí podmnožin přirozených jazyků, v nichž slova jazyka představují pojmy, které jsou spojeny s konkrétními významy nebo sémantikou . Ve výpočetní složitosti teorie , rozhodovací problémy jsou obvykle definována jako formálních jazyků a složitosti třídy jsou definovány jako množiny formálních jazyků, které mohou být analyzována pomocí strojů s omezenou výpočetní výkon. V logice a základech matematiky se používají formální jazyky k reprezentaci syntaxe axiomatických systémů a matematický formalismus je filozofie, že veškerou matematiku lze tímto způsobem redukovat na syntaktickou manipulaci formálních jazyků.

Dějiny

Za první použití formálního jazyka se považuje Gottlob Frege z roku 1879 Begriffsschrift , což znamená „pojmové psaní“, které pro čisté myšlení popisovalo „formální jazyk po vzoru aritmetiky“.

Axel Thueův raný semi-Thue systém , který lze použít k přepisování řetězců, měl vliv na formální gramatiky .

Slova nad abecedou

Abeceda , v rámci formálních jazyků, může být jakýkoliv soubor , i když to často smysl používat abecedu v obvyklém slova smyslu, nebo obecněji na znakovou sadu , například ASCII nebo Unicode . Prvkům abecedy se říká její písmena . Abeceda může obsahovat nekonečný počet prvků; většina definic v teorii formálních jazyků však uvádí abecedy s konečným počtem prvků a většina výsledků se vztahuje pouze na ně.

Slovo nad abecedou může být jakýkoliv konečnou sekvenci (tj řetězec ) dopisů. Množina všech slov nad abecedou usually je obvykle označena Σ * (pomocí Kleeneovy hvězdy ). Délka slova je počet písmen, ze kterých se skládá. Pro každou abecedu existuje pouze jedno slovo o délce 0, prázdné slovo , které je často označováno e, ε, λ nebo dokonce Λ. Podle zřetězení lze spojit dvě slova k vytvoření nové slovo, jehož je součet délek původních slov délky. Výsledkem zřetězení slova s ​​prázdným slovem je původní slovo.

V některých aplikacích, zejména v logice , je abeceda známá také jako slovní zásoba a slova jsou známá jako vzorce nebo věty ; tím se přeruší metafora dopisu/slova a nahradí se metaforou slova/věty.

Definice

Formální jazyk L nad abecedou? Je podmnožina of å * , tedy sadu slov během tohoto abecedy. Někdy jsou sady slov seskupeny do výrazů, zatímco pravidla a omezení mohou být formulována pro vytváření „dobře tvarovaných výrazů“.

V počítačové vědě a matematice, které se přirozeně nezabývají přirozenými jazyky , je přívlastek „formální“ často vynechán jako nadbytečný.

Zatímco teorie formálního jazyka se obvykle zabývá formálními jazyky, které jsou popsány některými syntaktickými pravidly, skutečná definice pojmu „formální jazyk“ je pouze výše: a (možná nekonečný) soubor řetězců konečné délky složený z dané abecedy, ne více a ne méně. V praxi existuje mnoho jazyků, které lze popsat pomocí pravidel, například běžné jazyky nebo jazyky bez kontextu . Pojem formální gramatiky může být bližší intuitivnímu pojmu „jazyk“, který je popsán syntaktickými pravidly. Zneužitím definice je určitý formální jazyk často považován za vybaven formální gramatikou, která jej popisuje.

Příklady

Následující pravidla popisují formální jazyk  L nad abecedou Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, =}:

  • Každý neprázdný řetězec, který neobsahuje „+“ nebo „=“ a nespustí se „0“, je v  L .
  • Řetězec „0“, je v  L .
  • Řetězec obsahující „=“ je v  L právě tehdy, když existuje právě jedna „=“, a to odděluje dvě platné řetězce  L .
  • Řetězec obsahující „+“, ale ne „=“ je v  L právě tehdy, když každý v řetězci „+“ odděluje dvě platné řetězce  L .
  • V L není žádný řetězec  kromě těch, které jsou obsaženy v předchozích pravidlech.

Podle těchto pravidel je řetězec „23+4 = 555“ v  L , ale řetězec „= 234 =+“ nikoli. Tento formální jazyk vyjadřuje přirozená čísla , dobře formované sčítání a dobře formované rovnosti sčítání, ale vyjadřuje pouze to, jak vypadají (jejich syntaxe ), nikoli to, co znamenají ( sémantika ). Například nikde v těchto pravidlech není žádný náznak, že „0“ znamená číslo nula, „+“ znamená sčítání, „23+4 = 555“ je nepravdivé atd.

Stavby

U konečných jazyků lze explicitně vyjmenovat všechna dobře formovaná slova. Například můžeme jazyk L popsat  jako pouhý L  = {a, b, ab, cba}. Degenerovaný případ této konstrukce je prázdný jazyk , který neobsahuje žádné slovo vůbec ( L  =  ).

Ale i přes konečnou (neprázdnou) abecedu, jako je Σ = {a, b}, existuje nekonečné množství slov s konečnou délkou, které lze potenciálně vyjádřit: „a“, „abb“, „ababba“, „ aaababbbbaab ", .... Formální jazyky jsou proto obvykle nekonečné a popis nekonečného formálního jazyka není tak jednoduchý jako psaní L  = {a, b, ab, cba}. Zde je několik příkladů formálních jazyků:

  • L = Σ * , množina všech slov nad Σ;
  • L = {a} * = {a n }, kde n se pohybuje nad přirozenými čísly a „a n “ znamená „a“ opakované nkrát (toto je sada slov, která se skládají pouze ze symbolu „a“);
  • množina syntakticky správných programů v daném programovacím jazyce (jehož syntaxe je obvykle definována bezkontextovou gramatikou );
  • množina vstupů, na kterých se určitý Turingův stroj zastaví; nebo
  • množina maximálních řetězců alfanumerických znaků ASCII na tomto řádku, tj.
    množina {the, set, of, maximum, strings, alphanumeric, ASCII, characters, on, this, line, i, e}.

Formality specifikující jazyk

Formální jazyky se používají jako nástroje ve více oborech. Teorie formálního jazyka se však jen zřídka zabývá konkrétními jazyky (kromě příkladů), ale zabývá se především studiem různých typů formalismů k popisu jazyků. Například jazyk může být uveden jako

Mezi typické otázky týkající se takových formalismů patří:

  • Jaká je jejich vyjadřovací síla? (Může formalismus X popsat každý jazyk, který může popsat formalismus Y ? Může popsat jiné jazyky?)
  • Jaká je jejich rozpoznatelnost? (Jak těžké je rozhodnout, zda dané slovo patří do jazyka popsaného formalismem X ?)
  • Jaká je jejich srovnatelnost? (Jak těžké je rozhodnout, zda dva jazyky, jeden popsaný ve formalismu X a jeden ve formalismu Y , nebo znovu v X , jsou ve skutečnosti stejný jazyk?).

Překvapivě často je odpověď na tyto rozhodovací problémy „nelze to udělat vůbec“ nebo „je to extrémně drahé“ (s charakterizací toho, jak drahé). Teorie formálního jazyka je proto hlavní aplikační oblastí teorie vypočítatelnosti a teorie složitosti . Formální jazyky lze v hierarchii Chomsky klasifikovat na základě expresivní síly jejich generativní gramatiky a složitosti jejich rozpoznávacího automatu . Gramatiky bez kontextu a běžné gramatiky poskytují dobrý kompromis mezi expresivitou a snadnou analýzou a jsou široce používány v praktických aplikacích.

Operace s jazyky

Některé operace s jazyky jsou běžné. To zahrnuje operace standardní sady, jako je sjednocení, průnik a doplněk. Další třídou operací je elementární aplikace řetězcových operací.

Příklady: Předpokládejme a jsou jazyky nad nějakým společným abecedy .

  • Zřetězení se skládá ze všech řetězců formuláře , kde je řetězec od a je řetězec z .
  • Křižovatka of a sestává ze všech řetězců, které jsou obsaženy v obou jazycích
  • Doplňkem of vzhledem ke skládá ze všech řetězců nad , které nejsou v .
  • Kleene hvězda : jazyk skládající se ze všech slov, která jsou zřetězení nula nebo více slov v původním jazyce;
  • Zvrat :
    • Nechť ε je prázdné slovo, pak , a
    • pro každé neprázdné slovo (kde jsou prvky nějaké abecedy) nechme ,
    • pak formální jazyk , .
  • Řetězcový homomorfismus

Takové řetězcové operace se používají ke zkoumání uzavíracích vlastností tříd jazyků. Třída jazyků je uzavřena v rámci konkrétní operace, když operace aplikovaná na jazyky ve třídě vždy znovu vytvoří jazyk ve stejné třídě. Například je známo , že bezkontextové jazyky jsou uzavřeny v rámci sjednocení, zřetězení a průniku s běžnými jazyky , ale nejsou uzavřeny v průsečíku nebo doplňku. Teorie trií a abstraktních rodin jazyků studuje nejběžnější uzavírací vlastnosti jazykových rodin samy o sobě.

Uzavírací vlastnosti jazykových rodin ( Op kde oba a jsou v jazykové rodině dané sloupcem). Po Hopcroftovi a Ullmanovi.
Úkon Pravidelný DCFL CFL IND CSL rekurzivní RE
svaz Ano Ne Ano Ano Ano Ano Ano
Průsečík Ano Ne Ne Ne Ano Ano Ano
Doplněk Ano Ano Ne Ne Ano Ano Ne
Zřetězení Ano Ne Ano Ano Ano Ano Ano
Kleeneova hvězda Ano Ne Ano Ano Ano Ano Ano
(Řetězec) homomorfismus Ano Ne Ano Ano Ne Ne Ano
Homomorfismus bez řetězců (e) Ano Ne Ano Ano Ano Ano Ano
Střídání Ano Ne Ano Ano Ano Ne Ano
Inverzní homomorfismus Ano Ano Ano Ano Ano Ano Ano
Zvrátit Ano Ne Ano Ano Ano Ano Ano
Křižovatka s běžným jazykem Ano Ano Ano Ano Ano Ano Ano

Aplikace

Programovací jazyky

Kompilátor má obvykle dvě odlišné komponenty. Lexikální analyzátor , někdy generované nástrojem, jako je lex, identifikuje žetony programovacího jazyka gramatiky, například identifikátory nebo klíčová slova , číselné a řetězcové literály, interpunkce a operátorské symboly, které jsou samy o sobě uvedeno jednodušším formálního jazyka, obvykle prostřednictvím pravidelného výrazy . Na nejzákladnější pojmového hlediska, je parser , někdy generováno generátor analyzátoru , jako je yacc, pokusy se rozhodnout, zda zdrojový program je syntakticky platí, že je-li dobře vytvořený s ohledem na programovací jazyk gramatiky, pro které byl překladač postaven.

Kompilátory samozřejmě dělají více než jen analyzují zdrojový kód - obvykle jej překládají do nějakého spustitelného formátu. Z tohoto důvodu analyzátor obvykle vydává více než odpověď ano/ne, obvykle abstraktní strom syntaxe . Toho používají následující fáze kompilátoru ke generování spustitelného souboru obsahujícího strojový kód, který běží přímo na hardwaru, nebo nějaký přechodný kód, který ke spuštění vyžaduje virtuální počítač .

Formální teorie, systémy a důkazy

Tento diagram ukazuje syntaktické rozdělení ve formálním systému . Řetězce symbolů lze široce rozdělit na nesmyslné a dobře formulované vzorce . Soubor dobře formulovaných vzorců je rozdělen na věty a non-věty.

V matematické logice je formální teorie soubor vět vyjádřených ve formálním jazyce.

Formální systém (také volal logický počet , nebo logický systém ) se skládá z formálního jazyka spolu s deduktivním zařízení (nazývaný také deduktivní systém ). Deduktivní aparát může sestávat ze sady transformačních pravidel , která mohou být interpretována jako platná pravidla pro odvození, nebo ze souboru axiomů , nebo mohou mít obojí. Formální systém se používá k odvození jednoho výrazu z jednoho nebo více dalších výrazů. Ačkoli formální jazyk lze identifikovat pomocí jeho vzorců, formální systém nelze také identifikovat podle jeho vět. Dva formální systémy a mohou mít všechny stejné věty a přesto se mohou lišit v některých významných důkazně teoretických způsobech (formule A může být syntaktickým důsledkem formule B v jedné, ale například ne v jiné).

Formální důkaz nebo derivace je konečná sekvence dobře vytvořených vzorců (které mohou být pokládány za vět, nebo tvrzení ), z nichž každý je axiom nebo vyplývá z výše uvedených obecných vzorcích v sekvenci o pravidlo závěru . Poslední věta v posloupnosti je větou formálního systému. Formální důkazy jsou užitečné, protože jejich věty lze interpretovat jako pravdivé věty.

Interpretace a modely

Formální jazyky jsou svou povahou zcela syntaktické, ale mohou mít danou sémantiku, která dává elementům jazyka smysl. Například v matematické logice je množina možných vzorců konkrétní logiky formálním jazykem a interpretace přiřadí význam každému ze vzorců - obvykle je to pravdivostní hodnota .

Studium výkladů formálních jazyků se nazývá formální sémantika . V matematické logice se to často dělá z hlediska teorie modelů . V teorii modelu jsou termíny, které se vyskytují ve vzorci, interpretovány jako objekty v rámci matematických struktur a pevná pravidla kompoziční interpretace určují, jak lze pravdivostní hodnotu vzorce odvodit z interpretace jejích pojmů; modelem pro vzorec je výklad pojmů, takže vzorec se stává pravdou.

Viz také

Poznámky

Reference

Citace

Prameny

Citované práce
Obecné reference

externí odkazy