Linjär grammatik

En linjär grammatik är en kontextfri grammatik så att den högra sidan av någon av dess slutledningsregler innehåller högst en icke-terminal.

Ett linjärt språk är ett språk som genereras av någon linjär grammatik.

Exempel

Ett enkelt exempel på en linjär grammatik är en med en uppsättning icke-terminaler , ett alfabet , en initial icke-terminal och inferensregler $G$ $N=\{S\}$ $\Sigma =\{a,b\}$ $S$

S\to aSb

S\to \varepsilon

Denna grammatik genererar ett oregelbundet språk . ${\displaystyle \{a^{i}b^{i}\;|\;i\geq 0\))$

Överensstämmelse med vanliga språk

Det finns speciella typer av linjär grammatik:

Vänsterlinjär grammatik, där icke-terminaler alltid är i början av de högra delarna av slutledningsreglerna;
En högerlinjär grammatik där icke-terminaler alltid är i slutet av de högra delarna av slutledningsreglerna.

Var och en av dessa typer beskriver individuellt exakt klassen av vanliga språk . En vanlig grammatik är en grammatik som är antingen vänsterlinjär eller högerlinjär.

En annan speciell typ av linjär grammatik är:

En linjär grammatik där icke-terminaler alltid finns antingen i början eller i slutet av den högra sidan av slutledningsreglerna.

Genom att lägga till nya icke-terminaler kan all linjär grammatik reduceras till den form som beskrivs ovan utan att ändra språket som genereras av grammatiken. Det kan till exempel föras till formuläret $G$

S\to aA

A\to Sb

S\to \varepsilon

Således genererar linjära grammatiker av detta slag samma klass av språk som godtyckliga linjära grammatiker.

Uttrycksförmåga

Alla vanliga språk är linjära. Det klassiska exemplet på ett linjärt men inte reguljärt språk är språket som beskrivs ovan . Alla linjära språk är kontextfria . Ett exempel på ett sammanhangsfritt men icke-linjärt språk är språket Dyck , som består av regelbundna parentessekvenser. Således är vanliga språk deras egen delmängd av linjära språk, som i sin tur är deras egen delmängd av sammanhangsfria språk. ${\displaystyle \{a^{i}b^{i}:i\geq 0\))$

Medan alla vanliga linjära språk är deterministiska , finns det icke-deterministiska linjära språk. Ett exempel på ett sådant språk är språket för palindromer med jämn längd över alfabetet , vilket ges av en linjär grammatik . Ett godtyckligt ord för ett givet språk kan inte analyseras av en pushdown-automat utan att läsa alla dess symboler, så språket är icke-deterministiskt [1] . Problemet med att kontrollera om ett givet sammanhangsfritt språk är linjärt är olösligt [2] . $\Sigma =\{0,1\}$ $S\to 0S0|1S1|\varepsilon$

Anteckningar

↑ Hopcroft JE , Motwani R. , Ullman JD Introduktion till automatteori, språk och beräkningar . — 2 uppl. - Addison-Wesley , 2001. - P. 249-253.
↑ Greibach, Sheila. Olösbarheten av erkännandet av linjära sammanhangsfria språk (engelska) // Journal of the ACM : journal. - 1966. - Oktober ( vol. 13 , nr 4 ). - doi : 10.1145/321356.321365 .