Gramatyka liniowa

W informatyce gramatyka liniowa to gramatyka bezkontekstowa , która ma co najwyżej jeden nieterminal po prawej stronie każdej ze swoich produkcji.

Język liniowy to język generowany przez pewną gramatykę liniową.

Przykład

Przykładem gramatyki liniowej jest G z N = {S}, Σ = {a, b}, P z symbolem startu S i regułami

S → aSb

S → ε

Generuje język ${\ Displaystyle \ {a ^ {i} b ^ {i} \;|\; i \ geq 0 \}}$ .

Związek z gramatyką regularną

Istnieją dwa specjalne typy gramatyk liniowych:

• gramatyki lewostronnie liniowe lub lewostronnie regularne, w których wszystkie reguły mają postać A → αw , gdzie α jest albo pustym, albo pojedynczym nieterminalem, a w jest ciągiem terminali;
• prawostronnie liniowe lub prawostronnie regularne, w których wszystkie reguły mają postać A → wα , gdzie w jest ciągiem końcówek, a α jest albo pusta, albo pojedynczym nieterminalem.

Każdy z nich może dokładnie opisywać języki regularne . Gramatyka regularna to gramatyka lewoliniowa lub prawoliniowa.

Zauważ, że wstawiając nowe nieterminale, każdą gramatykę liniową można zastąpić równoważną, w której niektóre reguły są lewoliniowe, a inne prawoliniowe. Na przykład zasady G powyżej można zastąpić

S → aA

A → Sb

S → ε

Jednak wymóg, aby wszystkie reguły były lewoliniowe (lub wszystkie reguły były prawoliniowe) prowadzi do ścisłego zmniejszenia mocy ekspresyjnej gramatyk liniowych.

Ekspresyjna moc

Wszystkie języki regularne są liniowe; odwrotnie, przykładem liniowego, nieregularnego języka jest { a ⁿ b ⁿ }. jak wyjaśniono powyżej. Wszystkie języki liniowe są bezkontekstowe ; odwrotnie, przykładem bezkontekstowego, nieliniowego języka jest język Dycka z dobrze wyważonymi parami nawiasów. Dlatego języki regularne są właściwym podzbiorem języków liniowych, które z kolei są właściwym podzbiorem języków bezkontekstowych.

Podczas gdy języki regularne są deterministyczne , istnieją języki liniowe, które są niedeterministyczne. Na przykład język palindromów parzystej długości na alfabecie 0 i 1 ma gramatykę liniową S → 0S0 | 1S1 | ε. Dowolny ciąg tego języka nie może być analizowany bez uprzedniego odczytania wszystkich jego liter, co oznacza, że ​​automat przesuwający w dół musi wypróbować alternatywne przejścia stanów, aby uwzględnić różne możliwe długości częściowo przeanalizowanego ciągu. Ten język jest niedeterministyczny. Ponieważ niedeterministyczne języki bezkontekstowe nie mogą być akceptowane w czasie liniowym, w ogólnym przypadku języki liniowe nie mogą być akceptowane w czasie liniowym. Ponadto nie można rozstrzygnąć, czy dany język bezkontekstowy jest liniowym językiem bezkontekstowym.

Język jest liniowy, jeśli można go wygenerować za pomocą automatu przesuwającego o jeden obrót — automatu przesuwającego, który, gdy zacznie strzelać, nigdy więcej nie naciska.

Właściwości zamknięcia

Przypadki pozytywne

Języki linearne są zamknięte w unii. Konstrukcja jest taka sama jak konstrukcja unii języków bezkontekstowych. Niech ${\ Displaystyle L_ {1}, L_ {2}}$ będą dwoma językami liniowymi, to jest skonstruowany przez gramatykę liniową ${\ Displaystyle L_ {1} \ puchar L_ {2}}$ gdzie ${\ Displaystyle S \ do S_ {1} | S_ {2}}$ i ${\ Displaystyle S_ {1}, S_ {2}}$ odgrywając rolę gramatyk liniowych dla ${\ Displaystyle L_ {1}, L_ {2}}$ .

Jeśli L jest językiem liniowym, a M $jest$ językiem regularnym, to przecięcie liniowym; innymi słowy, języki liniowe są zamknięte na przecięciu z regularnymi zbiorami.

Języki liniowe są zamknięte w homomorfizmie i homomorfizmie odwrotnym .

Wniosek: języki liniowe tworzą pełne trio . Ogólnie rzecz biorąc, pełne trio to rodziny języków, które mają kilka innych pożądanych właściwości matematycznych.

Negatywne przypadki

Języki liniowe nie są domknięte pod przecięciem. Na przykład niech ${\ Displaystyle L_ {1} = \ {a ^ {n} b ^ {n} c ^ {m} | n, m \ geq 0 \}, L_ {2} = \ {a ^ { n}b^{m}c^{m}|n,m\geq 0\}}$ , to ich przecięcie nie tylko nie jest liniowe, ale także nie jest bezkontekstowe. Zobacz lemat o pompowaniu dla języków bezkontekstowych .

W konsekwencji języki liniowe nie są domknięte pod dopełnieniem (ponieważ przecięcie może być skonstruowane przez prawa de Morgana z unii i dopełnienia).