I linguaggi non contestuali(context free) sono invece generabili con
grammatiche di tipo 2, coincidono con i linguaggi riconoscibili con automi a pila
non deterministici ed alcune loro sottoclassi sono sufficientemente ampie da
consentire di descrivere linguaggi di programmazione e al tempo stesso
sufficientemente ristrette da consentire la costruzione di analizzatori
sintattici(parser) che operano in tempo lineare.
Forma ridotta: grammatiche
prive di ε-produzioni,
prive di produzioni unitarie,
prive di produzioni che contengono simboli inutili (cioè simboli non
generabili partendo dall’assioma o simboli non fecondi, dai quali non si
generano stringhe di soli terminali).
I linguaggi non contestuali sono tutti e soli i linguaggi che vengono riconosciuti
da un automa a pila non deterministico (o automa "pushdown",PDA)
Def. Automa a pila non deterministico (PDA)
M=<Σ,Γ,Z0,Q,q0,F,δ>
Σ alfabeto di input
Γ alfabeto dei simboli della pila
Z0 ∈ Γ simbolo di pila iniziale
Q insieme finito di stati
q0 ∈ Q stato iniziale
Q ⊇ F insieme di stati finali
δ : Q ﾗ (Σ∪{ε}) ﾗ Γ → P(Q ﾗ Γ*)
Def. Linguaggio accettato dall'automa a pila:
due definizioni alternative
53