Neomezená gramatika - Unrestricted grammar

v teorie automatů, třída neomezené gramatiky (také zvaný napůl Čt, typ-0 nebo gramatiky frázové struktury) je nejobecnější třídou gramatik v Chomského hierarchie. Na produkce neomezené gramatiky se nevztahují žádná omezení, kromě toho, že každá z jejich levých stran je neprázdná.^[1]^:220 Tato třída gramatiky může generovat libovolné rekurzivně vyčíslitelné jazyky.

Formální definice

An neomezená gramatika je formální gramatika ${displaystyle G = (N, Sigma, P, S)}$ , kde ${displaystyle N}$ je konečná sada neterminálních symbolů, ${displaystyle Sigma}$ je konečná sada koncové symboly, ${displaystyle N}$ a ${displaystyle Sigma}$ jsou disjunktní,^{[poznámka 1]} ${displaystyle P}$ je konečná sada výrobní pravidla formuláře ${displaystyle alfa o eta}$ kde ${displaystyle alpha}$ a ${displaystyle eta}$ jsou řetězce symbolů v ${displaystyle Ncup Sigma}$ a ${displaystyle alpha}$ není prázdný řetězec a ${displaystyle Sin N}$ je speciálně určený počáteční symbol.^[1]^:220 Jak název napovídá, neexistují žádná skutečná omezení týkající se typů produkčních pravidel, která mohou mít neomezené gramatiky.^{[poznámka 2]}

Rovnocennost s Turingovými stroji

Neomezené gramatiky charakterizují rekurzivně vyčíslitelné jazyky. To je stejné jako říkat, že pro každou neomezenou gramatiku ${displaystyle G}$ nějaké existují Turingův stroj schopné rozpoznat ${displaystyle L (G)}$ a naopak. Vzhledem k neomezené gramatice je takový Turingův stroj dostatečně jednoduchý na to, aby se dal postavit, jako dvoustupňový nedeterministický Turingův stroj.^[1]^:221 První páska obsahuje vstupní slovo ${displaystyle w}$ které mají být testovány, a druhá páska je používána strojem ke generování vězeňské formuláře z ${displaystyle G}$ . Turingův stroj poté provede následující:

Začněte nalevo od druhé pásky a opakovaně se rozhodněte pohybovat doprava nebo vyberte aktuální pozici na kazetě.
Nedeterministicky vybrat produkci ${displaystyle eta o gamma}$ z produkce v ${displaystyle G}$ .
Li ${displaystyle eta}$ objeví se na nějaké pozici na druhé kazetě, vyměňte ji ${displaystyle eta}$ podle ${displaystyle gamma}$ v tomto bodě, případně posunutí symbolů na pásku doleva nebo doprava v závislosti na relativních délkách ${displaystyle eta}$ a ${displaystyle gamma}$ (např ${displaystyle eta}$ je delší než ${displaystyle gamma}$ , posuňte symboly pásky doleva).
Porovnejte výsledný sentenciální formulář na pásce 2 se slovem na pásce 1. Pokud se shodují, pak Turingův stroj slovo přijme. Pokud tak neučiní, Turingův stroj se vrátí ke kroku 1.

Je snadné vidět, že tento Turingův stroj bude generovat všechny a pouze sentenciální formy ${displaystyle G}$ na svém druhém pásku je po posledním kroku proveden libovolný počet opakování, tedy jazyk ${displaystyle L (G)}$ musí být rekurzivně spočetné.

Možná je i reverzní konstrukce. Vzhledem k určitému Turingovu stroji je možné vytvořit ekvivalentní neomezenou gramatiku^[1]^:222 který dokonce používá pouze inscenace s jedním nebo více nekoncovými symboly na levé straně. Proto lze libovolnou neomezenou gramatiku vždy ekvivalentně převést tak, aby vyhovovala druhé formě, a to převedením na Turingův stroj a zpět. Někteří autoři^{[Citace je zapotřebí ]} použít druhou formu jako definici neomezená gramatika.

Výpočtové vlastnosti

The rozhodovací problém zda daný řetězec ${displaystyle s}$ lze generovat danou neomezenou gramatikou, je ekvivalentní problému, zda ji může Turingův stroj přijmout jako gramatiku. Druhý problém se nazývá Zastavení problému a je nerozhodnutelný.

Rekurzivně vyčíslitelné jazyky jsou Zavřeno pod Kleene hvězda, zřetězení, svaz, a průsečík, ale ne pod nastavený rozdíl; vidět Rekurzivně vyčíslitelné vlastnosti jazyka # Uzavření.

Rovnocennost neomezených gramatik s Turingovými stroji implikuje existenci univerzální neomezené gramatiky, gramatiky schopné přijímat jakýkoli jiný neomezený jazyk gramatiky s daným popisem jazyka. Z tohoto důvodu je teoreticky možné postavit a programovací jazyk na základě neomezených gramatik (např. Čt ).

Viz také

Lambda kalkul
Systém Semi-Thue - nerozlišuje koncové a neterminální symboly, připouští prázdné levé strany

Poznámky

^ Ve skutečnosti to není nezbytně nutné, protože neomezené gramatiky mezi nimi nijak nerozlišují. Označení existuje čistě proto, aby člověk věděl, kdy přestat generovat vězeňské formuláře gramatiky; přesněji řečeno jazyk ${displaystyle L (G)}$ uznán ${displaystyle G}$ je omezeno na řetězce koncových symbolů
^ Zatímco Hopcroft a Ullman (1979) nezmínili kardinality ${displaystyle N}$ , ${displaystyle Sigma}$ , ${displaystyle P}$ výslovně důkaz jejich Věty 9.3 (konstrukce ekvivalentního Turingova stroje z dané neomezené gramatiky, str.221, srov. oddíl # Rovnocennost s Turingovými stroji ) mlčky vyžaduje konečnost ${displaystyle P}$ a konečné délky všech řetězců v pravidlech ${displaystyle P}$ . Každý člen skupiny ${displaystyle N}$ nebo ${displaystyle Sigma}$ který se nevyskytuje v ${displaystyle P}$ lze vynechat bez ovlivnění generovaného jazyka.

Reference

^ ^A ^b ^C ^d Hopcroft, Johne; Ullman, Jeffrey D. (1979). Úvod do teorie automatů, jazyků a výpočtu (1. vyd.). Addison-Wesley. ISBN 0-201-44124-1.

[2] Ve skutečnosti to není nezbytně nutné, protože neomezené gramatiky mezi nimi nijak nerozlišují. Označení existuje čistě proto, aby člověk věděl, kdy přestat generovat vězeňské formuláře gramatiky; přesněji řečeno jazyk ${displaystyle L (G)}$ uznán ${displaystyle G}$ je omezeno na řetězce koncových symbolů

[3] Zatímco Hopcroft a Ullman (1979) nezmínili kardinality ${displaystyle N}$ , ${displaystyle Sigma}$ , ${displaystyle P}$ výslovně důkaz jejich Věty 9.3 (konstrukce ekvivalentního Turingova stroje z dané neomezené gramatiky, str.221, srov. oddíl # Rovnocennost s Turingovými stroji ) mlčky vyžaduje konečnost ${displaystyle P}$ a konečné délky všech řetězců v pravidlech ${displaystyle P}$ . Každý člen skupiny ${displaystyle N}$ nebo ${displaystyle Sigma}$ který se nevyskytuje v ${displaystyle P}$ lze vynechat bez ovlivnění generovaného jazyka.

[Hopcroft.Ullman.1979-1] A ^b ^C ^d Hopcroft, Johne; Ullman, Jeffrey D. (1979). Úvod do teorie automatů, jazyků a výpočtu (1. vyd.). Addison-Wesley. ISBN 0-201-44124-1.

[1]

[poznámka 1]

[poznámka 2]