Lineární gramatika

Lineární gramatika je bezkontextová gramatika , takže pravá strana kteréhokoli z jejích odvozovacích pravidel obsahuje nejvýše jeden neterminál.

Lineární jazyk je jazyk generovaný nějakou lineární gramatikou.

Příklad

Jednoduchý příklad lineární gramatiky je gramatika se sadou neterminálů , abecedou , počátečním neterminálem a pravidly odvození. $G$ $N=\{S\}$ $\Sigma =\{a,b\}$ $S$

S\to aSb

S\to \varepsilon

Tato gramatika generuje nepravidelný jazyk . ${\displaystyle \{a^{i}b^{i}\;|\;i\geq 0\))$

Soulad s běžnými jazyky

Existují speciální typy lineárních gramatik:

Levolineární gramatika, ve které jsou neterminály vždy na začátku pravých částí odvozovacích pravidel;
Pravolineární gramatika, ve které jsou neterminály vždy na konci správných částí odvozovacích pravidel.

Každý z těchto typů jednotlivě přesně popisuje třídu regulárních jazyků . Regulární gramatika je gramatika, která je buď levá lineární, nebo pravá lineární.

Dalším speciálním typem lineární gramatiky je:

Lineární gramatika, ve které se neterminály vždy nacházejí buď na začátku nebo na konci pravé strany odvozovacích pravidel.

Přidáním nových neterminálů lze libovolnou lineární gramatiku redukovat do výše popsané formy beze změny jazyka generovaného gramatikou. Může být například přenesen do formuláře $G$

S\to aA

A\to Sb

S\to \varepsilon

Lineární gramatiky tohoto druhu tedy generují stejnou třídu jazyků jako libovolné lineární gramatiky.

Expresivita

Všechny běžné jazyky jsou lineární. Klasickým příkladem lineárního, ale ne regulárního jazyka je jazyk popsaný výše . Všechny lineární jazyky jsou bezkontextové . Příkladem bezkontextového, ale nelineárního jazyka je jazyk Dyck , který se skládá z pravidelných závorkových sekvencí. Regulární jazyky jsou tedy jejich vlastní podmnožinou lineárních jazyků, které jsou zase jejich vlastní podmnožinou bezkontextových jazyků. ${\displaystyle \{a^{i}b^{i}:i\geq 0\))$

Zatímco všechny běžné lineární jazyky jsou deterministické , existují nedeterministické lineární jazyky. Příkladem takového jazyka je jazyk palindromů sudé délky nad abecedou , který je dán lineární gramatikou . Libovolné slovo daného jazyka nemůže být analyzováno zásobníkovým automatem bez přečtení všech jeho symbolů, takže jazyk je nedeterministický [1] . Problém kontroly, zda je daný bezkontextový jazyk lineární, je neřešitelný [2] . $\Sigma =\{0,1\}$ $S\to 0S0|1S1|\varepsilon$

Poznámky

↑ Hopcroft JE , Motwani R. , Ullman JD Úvod do teorie automatů, jazyků a počítání . — 2 ed. - Addison-Wesley , 2001. - S. 249-253.
↑ Greibach, Sheila. Neřešitelnost rozpoznávání lineárních bezkontextových jazyků (anglicky) // Journal of the ACM : journal. - 1966. - říjen ( roč. 13 , č. 4 ). - doi : 10.1145/321356.321365 .