Ierarhia Chomsky

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

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).

Gramatici formale[modificare | modificare sursă]

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 \epsilon 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

Ierarhia[modificare | modificare sursă]

Ierarhia Chomsky constă din următoarele nivele:

  • 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 \alpha, \beta și \gamma șiruri de terminali și neterminali. Șirurile \alpha și \beta pot fi vide, dar \gamma 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 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 si

sau A \rightarrow aB
ori A \rightarrow Ba

Bibliografie[modificare | modificare sursă]

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

Alte legături[modificare | modificare sursă]