Limbaj fără context

Un limbaj liber din context (sau non-contextual sau fără context) este un limbaj formal generat de o gramatică care nu este, tocmai contextuală , adică astfel încât regulile acționează asupra simbolurilor non-terminale, indiferent de context în care apar.

Setul de limbaje fără context este echivalent cu setul de limbaje care sunt recunoscute de un automat stivă nedeterminist . Simplitatea tipului de automat necesar recunoașterii lor și faptul că acesta poate fi generat direct din definiția gramaticale fac ca această clasă de limbaje să prezinte un interes deosebit în informatică teoretică și în special în teoria limbajelor de programare și a acestora. implementare.

Exemple

Un arhetip de limbaj fără context este $L=\{a^{n}b^{n}:n\geq 1\}$ ${\ displaystyle L = \ {a ^ {n} b ^ {n}: n \ geq 1 \}}$ $L = \ {a ^ {n} b ^ {n}: n \ geq 1 \}$ , limbajul tuturor corzilor de lungime uniformă, din care prima jumătate este compusă din $la$ ${\ displaystyle a}$ $la$ , iar a doua jumătate de la $b$ ${\ displaystyle b}$ $b$ . Limba $L$ ${\ displaystyle L}$ $L$ este generată de gramatică $S\to aSb~|~ab$ ${\ displaystyle S \ to aSb ~ | ~ ab}$ $S \ to aSb ~ | ~ ab$ , și este acceptat de automatul pushdown $M=(\{q_{0},q_{1},q_{f}\},\{a\},\{a,b,z\},\delta ,q_{0},\{q_{f}\})$ ${\ displaystyle M = (\ {q_ {0}, q_ {1}, q_ {f} \}, \ {a \}, \ {a, b, z \}, \ delta, q_ {0}, \ {q_ {f} \})}$ $M = (\ {q_ {0}, q_ {1}, q_ {f} \}, \ {a \}, \ {a, b, z \}, \ delta, q_ {0}, \ {q_ { f} \})$ unde este $\delta$ ${\ displaystyle \ delta}$ $\ delta$ este definit astfel:

$\delta (q_{1},a,z)=(q_{0},a)$ ${\ displaystyle \ delta (q_ {1}, a, z) = (q_ {0}, a)}$ $\ delta (q_ {1}, a, z) = (q_ {0}, a)$
$\delta (q_{2},b,ax)=(q_{1},x)$ ${\ displaystyle \ delta (q_ {2}, b, ax) = (q_ {1}, x)}$ $\ delta (q_ {2}, b, ax) = (q_ {1}, x)$
$\delta (q_{0},b,ax)=(q_{1},x)$ ${\ displaystyle \ delta (q_ {0}, b, ax) = (q_ {1}, x)}$ $\ delta (q_ {0}, b, ax) = (q_ {1}, x)$
$\delta (q_{2},b,bz)=(q_{f},z)$ ${\ displaystyle \ delta (q_ {2}, b, bz) = (q_ {f}, z)}$ $\ delta (q_ {2}, b, bz) = (q_ {f}, z)$

Limbajele fără context au multe aplicații în limbaje de programare ; de exemplu, limba care verifică dacă parantezele sunt potrivite corect este generată de gramatică $S\to SS~|~(S)~|~\lambda$ ${\ displaystyle S \ to SS ~ | ~ (S) ~ | ~ \ lambda}$ $S \ to SS ~ | ~ (S) ~ | ~ \ lambda$ .
Mai mult, expresiile aritmetice sunt generate de gramatici fără context și neregulate. ^[1]

Proprietate

Familia de limbi fără context este închisă pentru concatenare și unire, dar nu pentru intersecție sau diferență. În orice caz, este închis pentru intersecție și diferență cu limbaje liniare . ^[2]
Având în vedere o gramatică de tip 2 G, este decis să se stabilească dacă generează un limbaj gol ( $L(G)=\emptyset$ ${\ displaystyle L (G) = \ emptyset}$ $L (G) = \ emptyset$ ). ^[3]
Având în vedere o gramatică de tip 2 G, este decis să se stabilească dacă generează un limbaj infinit. ^[4]

Notă

^ http://www.cs.odu.edu/~toida/nerzic/390teched/regular/reg-lang/non-regularity.html
^ Ausiello, 2003 , pp. 136-138 .
^ Ausiello, 2003 , pp. 138 .
^ Ausiello, 2003 , pp. 139 .

Bibliografie

Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi, Limbaje de modelare a complexității, Milano, Franco Angeli Editore, 2003, ISBN 88-464-4470-1 .

Elemente conexe

Lema de pompare oferă condiții necesare (dar nu suficiente) pentru ca limbile fără context să fie regulate.

Alte proiecte

Wikiversitatea conține o lecție despre Limbajul fără context

Teoria automatelor : limbaje formale și gramatici formale
Ierarhia Chomsky	Gramatica formală	Limba	Automat minim
Tipul-0	(nelimitat)	Recursiv enumerabil	Mașină Turing
	(nelimitat)	Recursiv	Decider
Tipul 1	Context dependent	Context dependent	Automat liniar
Tipul 2	Fără context	Fără context	Automat cu baterie ND
Tipul 3	Regulat	Regulat	Stări finite
Fiecare categorie de limbă sau gramatică este un subset adecvat al categoriei imediat deasupra acesteia.

Portal IT

Portalul de matematică

[1] ttp://www.cs.odu.edu/~toida/nerzic/390teched/regular/reg-lang/non-regularity.html

[2] Ausiello, 2003 , pp. 136-138 .

[3] Ausiello, 2003 , pp. 138 .

[4] Ausiello, 2003 , pp. 139 .

[1]

[2]

[3]

[4]