Sisteme de rescriere (Recap) Gramatici generative şi analitice Gramatici - Exemple diverse Ierarhia lui Chomsky Operaţii cu limbaje

Curs Limbaje formale şi compilatoare

Gramatici

Universitatea Transilvania din Braşov

Facultatea de Matematică şi Informatică

2023
Sisteme de rescriere (Recap) Gramatici generative şi analitice Gramatici - Exemple diverse Ierarhia lui Chomsky Operaţii cu limbaje

Agenda

1 Sisteme de rescriere (Recap)

2 Gramatici generative şi analitice

3 Gramatici - Exemple diverse

4 Ierarhia lui Chomsky

5 Operaţii cu limbaje
Sisteme de rescriere (Recap) Gramatici generative şi analitice Gramatici - Exemple diverse Ierarhia lui Chomsky Operaţii cu limbaje

Sisteme de rescriere

Sistem de rescriere. Se numeşte sistem de rescriere o pereche ordonată

SR = (F , V ), unde V este un alfabet iar F o mulţime de perechi ordonate de
cuvinte peste V . Elementele (α, β) ∈ F se numesc reguli de rescriere sau
producţii şi se notează α → β.
Derivaţie. Un cuvânt α peste V generază direct un cuvânt β, α ⇒ β, dacă şi
numai dacă ∃u, v , α1 , β1 ∈ V ∗ astfel încât: α = uα1 v , β = uβ1 v şi α1 → β1 .
Sisteme de rescriere (Recap) Gramatici generative şi analitice Gramatici - Exemple diverse Ierarhia lui Chomsky Operaţii cu limbaje

Gramatici generative

Gramatică generativă se numeşte un cvadruplu ordonat G = (VN , VT , S, P)

unde
VN = mulţimea neterminalelor, alfabet finit nevid
T
VT = mulţimea terminalelor, alfabet finit nevid şi VT VN = ∅
S ∈ VN = simbolul de start
P = o mulţime finită de perechi ordonate (u, v ), u, v ∈ (VN VT )∗ şi u conţine
S
cel puţin un element din VN . Elementele lui P se numesc producţii şi se
notează u → v .
∗
Limbajul generat de G: L(G) = {w|w ∈ VT∗ , S ⇒ w}.
Sisteme de rescriere (Recap) Gramatici generative şi analitice Gramatici - Exemple diverse Ierarhia lui Chomsky Operaţii cu limbaje

Gramatici analitică

Gramatică analitică se numeşte un cvadruplu ordonat G = (VN , VT , S, P)

unde VN , VT şi S au aceeaşi semnificaţie ca şi pentru gramatici generative,
iar P este o mulţime de reguli (u, v ), u, v ∈ (VN VT )∗ şi v conţine cel puţin
S
un element din VN .
∗
Limbaj recunoscut de G: L(G) = {w|w ∈ VT∗ , w ⇒ S}.
Sisteme de rescriere (Recap) Gramatici generative şi analitice Gramatici - Exemple diverse Ierarhia lui Chomsky Operaţii cu limbaje

Gramatici - Exemple

Limbajul L = {ai bi |i ∈ N} este generat de gramatica generativă

G = ({S}, {a, b}, S, {S− > λ, S− > aSb}) şi recunoscut de gramatica
analitică G1 = ({S}, {a, b}, S, {λ− > S, aSb− > S}).
Deci L(G) = L(G1).
Sisteme de rescriere (Recap) Gramatici generative şi analitice Gramatici - Exemple diverse Ierarhia lui Chomsky Operaţii cu limbaje

Ierarhia lui Chomsky (I)

Gramatici echivalente. Spunem că două gramatici G şi G1 sunt echivalente,

dacă şi numai dacă L(G) = L(G1 ).
Observaţie: Pentru orice gramatică generativă există o gramatică analitică
echivalentă şi reciproc.
Ierarhia lui Chomsky: Orice gramatică generativă G = (VN , VT , S, P) poate
fi clasificate în modul următor, în funcţie de anumite restricţii asupra
producţiilor sale:
(0) Gramatică de tip 0 care nu are nici o restricţie asupra regulilor;
Sisteme de rescriere (Recap) Gramatici generative şi analitice Gramatici - Exemple diverse Ierarhia lui Chomsky Operaţii cu limbaje

Ierarhia lui Chomsky (I)

Gramatici echivalente. Spunem că două gramatici G şi G1 sunt echivalente,

dacă şi numai dacă L(G) = L(G1 ).
Observaţie: Pentru orice gramatică generativă există o gramatică analitică
echivalentă şi reciproc.
Ierarhia lui Chomsky: Orice gramatică generativă G = (VN , VT , S, P) poate
fi clasificate în modul următor, în funcţie de anumite restricţii asupra
producţiilor sale:
(0) Gramatică de tip 0 care nu are nici o restricţie asupra regulilor;
(1) Gramatică de tip 1 sau dependentă de context (DC) în care fiecare
u1 Au2 → u1 wu2 , unde u1 , u2 ∈ (VN VT )∗ ,
S
regulă din P este de
Sforma
A ∈ VN şi w ∈ (VN VT )+ cu o singură excepţie posibilă S → λ, care
poate să apară dacă S nu apare în dreapta nici unei reguli din P.
Sisteme de rescriere (Recap) Gramatici generative şi analitice Gramatici - Exemple diverse Ierarhia lui Chomsky Operaţii cu limbaje

Ierarhia lui Chomsky (I)

Gramatici echivalente. Spunem că două gramatici G şi G1 sunt echivalente,

dacă şi numai dacă L(G) = L(G1 ).
Observaţie: Pentru orice gramatică generativă există o gramatică analitică
echivalentă şi reciproc.
Ierarhia lui Chomsky: Orice gramatică generativă G = (VN , VT , S, P) poate
fi clasificate în modul următor, în funcţie de anumite restricţii asupra
producţiilor sale:
(0) Gramatică de tip 0 care nu are nici o restricţie asupra regulilor;
(1) Gramatică de tip 1 sau dependentă de context (DC) în care fiecare
u1 Au2 → u1 wu2 , unde u1 , u2 ∈ (VN VT )∗ ,
S
regulă din P este de
Sforma
A ∈ VN şi w ∈ (VN VT )+ cu o singură excepţie posibilă S → λ, care
poate să apară dacă S nu apare în dreapta nici unei reguli din P.
(2) Gramatică de tip 2 sau independentă de context (IDC) în
S care fiecare
regulă din P este de forma A → w cu A ∈ VN şi w ∈ (VN VT )+ .
Sisteme de rescriere (Recap) Gramatici generative şi analitice Gramatici - Exemple diverse Ierarhia lui Chomsky Operaţii cu limbaje

Ierarhia lui Chomsky (I)

Gramatici echivalente. Spunem că două gramatici G şi G1 sunt echivalente,

dacă şi numai dacă L(G) = L(G1 ).
Observaţie: Pentru orice gramatică generativă există o gramatică analitică
echivalentă şi reciproc.
Ierarhia lui Chomsky: Orice gramatică generativă G = (VN , VT , S, P) poate
fi clasificate în modul următor, în funcţie de anumite restricţii asupra
producţiilor sale:
(0) Gramatică de tip 0 care nu are nici o restricţie asupra regulilor;
(1) Gramatică de tip 1 sau dependentă de context (DC) în care fiecare
u1 Au2 → u1 wu2 , unde u1 , u2 ∈ (VN VT )∗ ,
S
regulă din P este de
Sforma
A ∈ VN şi w ∈ (VN VT )+ cu o singură excepţie posibilă S → λ, care
poate să apară dacă S nu apare în dreapta nici unei reguli din P.
(2) Gramatică de tip 2 sau independentă de context (IDC) în
S care fiecare
regulă din P este de forma A → w cu A ∈ VN şi w ∈ (VN VT )+ .
(3) Gramatică de tip 3 sau regulată (R) în care fiecare regulă are una dintre
următoarele două forme: A → aB sau A → a, unde A, B ∈ VN şi a ∈ VT
Sisteme de rescriere (Recap) Gramatici generative şi analitice Gramatici - Exemple diverse Ierarhia lui Chomsky Operaţii cu limbaje

Ierarhia lui Chomsky (II)

Gramaticile de tip 1 se numesc dependente de context sau

contextuale

Evident că orice gramatică de tip 3 este şi de tip 2, orice gramatică de tip 2
este şi de tip 1, şi orice gramatică de tip 1 este de tip 0.
Sisteme de rescriere (Recap) Gramatici generative şi analitice Gramatici - Exemple diverse Ierarhia lui Chomsky Operaţii cu limbaje

Ierarhia lui Chomsky (II)

Gramaticile de tip 1 se numesc dependente de context sau

contextuale
Gramaticile de tip 2 se numesc independente de context

Evident că orice gramatică de tip 3 este şi de tip 2, orice gramatică de tip 2
este şi de tip 1, şi orice gramatică de tip 1 este de tip 0.
Sisteme de rescriere (Recap) Gramatici generative şi analitice Gramatici - Exemple diverse Ierarhia lui Chomsky Operaţii cu limbaje

Ierarhia lui Chomsky (II)

Gramaticile de tip 1 se numesc dependente de context sau

contextuale
Gramaticile de tip 2 se numesc independente de context
Gramaticile de tip 3 se numesc regulate sau cu număr finit de stări

Evident că orice gramatică de tip 3 este şi de tip 2, orice gramatică de tip 2
este şi de tip 1, şi orice gramatică de tip 1 este de tip 0.
Sisteme de rescriere (Recap) Gramatici generative şi analitice Gramatici - Exemple diverse Ierarhia lui Chomsky Operaţii cu limbaje

Operaţii cu limbaje

Deoarece limbajele sunt mulţimi, se pot utiliza operaţiile pentru mulţimi.

S
Reuniunea a două limbaje: L1 T L2 = {w|w ∈ L1 sau w ∈ L2 }
Intersecţia a două limbaje: L1 L2 = {w|w ∈ L1 şi w ∈ L2 }
Diferenţa a două limbaje: L1 − L2 = {w|w ∈ L1 şi w ∈ / L2 }
Alte operaţii specifice limbajelor:
Concatenarea a două limbaje: L1 L2 = {uv |u ∈ L1 , v ∈ L2 }
Puterea unui limbaj: se defineşte recursiv prin L0 = λ, Li+1 = Li L
∞
Produsul (închiderea) Kleene: L∗ = Li
S
i=0
Câtul stâng a două limbaje: L1 \L2 = {v |uv ∈ L1 , u ∈ L2 }
Câtul drept a două limbaje: L1 /L2 = {v |vu ∈ L1 , u ∈ L2 }
L = {u
Reflectatul (oglinditul) unui limbaj: e e|u ∈ L}
Sisteme de rescriere (Recap) Gramatici generative şi analitice Gramatici - Exemple diverse Ierarhia lui Chomsky Operaţii cu limbaje

Gramatici generative. Exerciţii.

Ce este o gramatică generativă? Câte tipuri de gramatici cunoaşteţi şi

care sunt acestea?
Sisteme de rescriere (Recap) Gramatici generative şi analitice Gramatici - Exemple diverse Ierarhia lui Chomsky Operaţii cu limbaje

Gramatici generative. Exerciţii.

Ce este o gramatică generativă? Câte tipuri de gramatici cunoaşteţi şi

care sunt acestea?
Se dă gramatica G = (VN , VT , S, P) cu VN = {S, A},
VT = {∧, ∨, ¬, p, q, r ,′ }, P = {S → ∧SS, S → ∨SS, S → ¬S, S →
A, A → A′ , A → p, A → q, A → r }.
Să se verifice dacă ∧ ∨ ∧ ∨ pqr ∧ pqr ∈ L(G).
Sisteme de rescriere (Recap) Gramatici generative şi analitice Gramatici - Exemple diverse Ierarhia lui Chomsky Operaţii cu limbaje

Gramatici generative. Exerciţii.

Ce este o gramatică generativă? Câte tipuri de gramatici cunoaşteţi şi

care sunt acestea?
Se dă gramatica G = (VN , VT , S, P) cu VN = {S, A},
VT = {∧, ∨, ¬, p, q, r ,′ }, P = {S → ∧SS, S → ∨SS, S → ¬S, S →
A, A → A′ , A → p, A → q, A → r }.
Să se verifice dacă ∧ ∨ ∧ ∨ pqr ∧ pqr ∈ L(G).
Să se construiască gramatica pentru generarea limbajului:

L = an bn |n > 0

Sisteme de rescriere (Recap) Gramatici generative şi analitice Gramatici - Exemple diverse Ierarhia lui Chomsky Operaţii cu limbaje

Gramatici generative. Exerciţii.

Ce este o gramatică generativă? Câte tipuri de gramatici cunoaşteţi şi

care sunt acestea?
Se dă gramatica G = (VN , VT , S, P) cu VN = {S, A},
VT = {∧, ∨, ¬, p, q, r ,′ }, P = {S → ∧SS, S → ∨SS, S → ¬S, S →
A, A → A′ , A → p, A → q, A → r }.
Să se verifice dacă ∧ ∨ ∧ ∨ pqr ∧ pqr ∈ L(G).
Să se construiască gramatica pentru generarea limbajului:

L = an bn |n > 0


Fie gramatica G = ({S, A, C}, {a, b, c}, S, P) cu P:

S → abAC
A → aAb|ab
C → cC|c
(a) De ce tip este această gramatică?
(b) Să se verifice dacă cuvântul abaaabbbc aparţine limbajului L(G).
(c) Să se determine 3 cuvinte care aparţin limbajului generat de G.