Ierarhia Chomsky

De la Wikipedia, enciclopedia liberă

Ierarhia Chomsky este o ierarhie de incluziune a claselor de gramatici formale care generează limbaje formale. Ierarhia acestor gramatici, numite şi gramatici de structură a frazelor, a fost descrise de Noam Chomsky în 1956 (vezi bibliografia).

[modifică] Gramatici formale

O gramatică formală constă dintr-o mulţime finită de simboluri terminale (literele cuvântului din limbajul formal), o mulţime finită de simboluri neterminale, o mulţime finită de reguli de producţie care au o parte stângă şi una dreaptă, ambele constând dintr-un cuvânt format din aceste două tipuri de simboluri, şi un simbol de start. O regulă se poate aplica unui cuvânt prin înlocuirea părţii stângi cu cea dreaptă. O derivare reprezintă o succesiune de aplicări ale regulilor de producţie. O astfel de gramatică defineşte limbajul formal al tuturor cuvintelor constând numai din simboluri terminale la care se poate ajunge printr.o derivare din simbolul de start.

Neterminalii sunt în general reprezentaţi prin litere mari, terminalii prin litere mici, şi simbolul de start prin $S$ . De exemplu, gramatica cu terminalii ${a, b}$ , neterminalii ${S, A, B}$ , regulile de producţie

$S \rightarrow ABS$

$S \rightarrow \epsilon$ (unde

ε

este şirul vid)

$BA \rightarrow AB$

$BS \rightarrow b$

$Bb \rightarrow bb$

$Ab \rightarrow ab$

$Aa \rightarrow aa$

şi simbolul de start $S$ , defineşte limbajul tuturor cuvintelor de forma $a n b n$ (adică $n$ copii ale lui $a$ urmate de $n$ copii ale lui $b$ ). Următoarea gramatică defineşte un limbaj similar: Terminalii ${p, q}$ , Neterminalii ${S}$ , Simbolul de start $S$ , Regulile de producţie

$S \rightarrow pSq$

$S \rightarrow \epsilon$

[modifică] Ierarhia

Ierarhia Chomsky constă din următoarele nivele:

Gramaticile de tip 0 (gramatici nerestricţionate) includ toate gramaticile formale. Ele generează exact toate limbajele care pot fi recunoscute de o maşină Turing. Aceste limbaje sunt cunoscute şi sub numele de limbaje recursiv enumerabile. De notat că acestea sunt diferite de limbajele recursive care pot fi decise de o maşină Turing care se opreşte întotdeauna

Gramaticile de tip 1 (gramatici dependente de context) generează limbaje dependente de context. Aceste gramatici au reguli de forma $\alpha A\beta \rightarrow \alpha\gamma\beta$ cu $A$ neterminal şi $α$ , $β$ şi $γ$ şiruri de terminali şi neterminali. Şirurile $α$ şi $β$ pot fi vide, dar $γ$ trebuie să fie nevid. Regula $S \rightarrow \epsilon$ este permisă dacă $S$ nu apare în partea dreaptă a vreunei reguli. Limbajele descrise de aceste gramatici sunt exact toate limbajele care pot fi recunoscute de o maşină Turing nedeterministă a cărei bandă este limitată de o constantă înmulţită cu lungimea intrării.

Gramaticile de tip 2 (gramatici independente de context) generează limbaje independente de context. Acestea sunt definite ca reguli de forma $A \rightarrow \gamma$ cu $A$ neterminal şi $γ$ un şir de terminali şi neterminali. Aceste limbaje sunt exact toate limbajele care pot fi recunoscute de un automat cu stivă nedeterminist. Limbajele independente de context constituie baza teoretică a majorităţii limbajelor de programare.

Gramaticile de tip 3 (gramatici regulate) generează limbaje regulate. O astfel de gramatică restrânge regulile la un singur neterminal pe partea stângă şi o parte dreaptă constând dintr-un singur terminal, care poate fi urmat (sau precedat, dar nu ambele în aceeaşi gramatică) de un singur neterminal. Regula $S \rightarrow \epsilon$ este şi ea permisă dacă $S$ nu apare în partea stângă a vreunei reguli. Aceste limbaje sunt exact toate limbajele care pot fi decise de un automat finit. În plus, această familie de limbaje formale poate fi obţinută cu ajutorul expresiilor regulate. Limbajele regulate sunt utilizate în general pentru a căuta şabloane şi în structura lexicală a limbajelor de programare.

De notat că mulţimea gramaticilor care corespund limbajelor recursive nu este membră a acestei ierarhii.

Toate limbajele regulate sunt şi independente de context, toate limbajele independente de context sunt şi limbaje dependente de context şi toate limbajele dependente de context sunt şi recursive şi toate limbajele recursive sunt şi recursiv enumerabile. Acestea sunt toate incluziuni stricte, adică există limbaje recursiv enumerabille care nu sunt recursive, limbaje recursive care nu sunt dependente de context, limbaje dependente de context care nu sunt independente de context şi limbaje independente de context care nu sunt regulate.

Următoarea tabelă rezumă fiecare din cele patru tipuri de gramatici ale lui Chomsky, clasele de limbaje pe care le generează, tipul de automat care le recunoaşte şi forma regulilor de producţie.

Gramatică	Limbaj	Automat	Reguli de producţie
Recursiv enumerabile	limbaje recursiv enumerabile	maşină Turing	Nici o restricţie
Dependentă de context	limbaje dependente de context	maşină Turing nedeterministă limitată liniar	$\alpha A\beta \rightarrow \alpha\gamma\beta$
Independentă de context	limbaje independente de context	automat cu stivă nedeterminist	$A \rightarrow \gamma$
Regulată	limbaje regulate	automat finit cu stări	$A \rightarrow a$ and either $A \rightarrow aB$ or $A \rightarrow Ba$

[modifică] Bibliografie

Noam Chomsky: Three models for the description of language, IRE Transactions on Information Theory, 2 (1956), pages 113-124
Noam Chomsky: On certain formal properties of grammars, Information and Control, 1 (1959), pages 91-112