Lineáris nyelvtan

A lineáris nyelvtan olyan környezetfüggetlen nyelvtan , amelynek bármely következtetési szabályának jobb oldala legfeljebb egy nem terminált tartalmaz.

A lineáris nyelv egy lineáris nyelvtan által generált nyelv.

Példa

Egy egyszerű példa a lineáris nyelvtanra egy nemterminális készlettel , egy ábécével , egy kezdő nemterminálissal és következtetési szabályokkal. $G$ $N=\{S\}$ $\Sigma =\{a,b\}$ $S$

S\to aSb

S\to \varepsilon

Ez a nyelvtan szabálytalan nyelvet generál . ${\displaystyle \{a^{i}b^{i}\;|\;i\geq 0\))$

Megfelelés a normál nyelveknek

A lineáris nyelvtanoknak speciális típusai vannak:

Bal-lineáris nyelvtan, amelyben a nem terminálisok mindig a következtetési szabályok jobb részének elején vannak;
Egy jobb-lineáris nyelvtan, amelyben a nem terminálisok mindig a következtetési szabályok jobb oldali részének végén vannak.

Ezen típusok mindegyike külön-külön pontosan leírja a reguláris nyelvek osztályát . A szabályos nyelvtan egy olyan nyelvtan, amely vagy bal-lineáris vagy jobb-lineáris.

A lineáris nyelvtan egy másik speciális típusa:

Lineáris nyelvtan, amelyben a nem terminálisok mindig a következtetési szabályok jobb oldalának elején vagy végén találhatók.

Új nem terminálok hozzáadásával bármely lineáris nyelvtan a fent leírt formára redukálható anélkül, hogy a nyelvtan által generált nyelv megváltozna. Például formába hozható $G$

S\to aA

A\to Sb

S\to \varepsilon

Így az ilyen típusú lineáris nyelvtanok ugyanazt a nyelvosztályt generálják, mint az önkényes lineáris nyelvtanok.

Kifejezőség

Minden reguláris nyelv lineáris. A lineáris, de nem reguláris nyelv klasszikus példája a fent leírt nyelv . Minden lineáris nyelv környezetfüggetlen . A környezetfüggetlen, de nem lineáris nyelvre példa a Dyck nyelv , amely szabályos zárójelsorozatokból áll. Így a reguláris nyelvek a lineáris nyelvek saját részhalmazai , amelyek viszont a kontextusmentes nyelvek saját részhalmazai. $\{a^{i}b^{i}:i\geq 0\}$

Míg minden reguláris lineáris nyelv determinisztikus , vannak nem determinisztikus lineáris nyelvek. Ilyen nyelv például az ábécé feletti egyenletes hosszúságú palindromok nyelve , amelyet egy lineáris nyelvtan ad meg . Egy adott nyelv tetszőleges szavát nem tudja egy lenyomó automata elemezni anélkül, hogy elolvasná az összes szimbólumát, ezért a nyelv nem determinisztikus [1] . Az a probléma, hogy egy adott kontextusmentes nyelv lineáris-e, megoldhatatlan [2] . $\Sigma =\{0,1\}$ $S\to 0S0|1S1|\varepsilon$

Jegyzetek

↑ Hopcroft JE , Motwani R. , Ullman JD . Bevezetés az automataelméletbe, nyelvekbe és számításba . — 2 ed. - Addison-Wesley , 2001. - P. 249-253.
↑ Greibach, Sheila. A lineáris kontextusmentes nyelvek felismerésének megoldhatatlansága (angol) // Journal of the ACM : Journal. - 1966. - október ( 13. évf. , 4. sz.). - doi : 10.1145/321356.321365 .