În știința teoretică de calculator , teoria limbajului și calculabilitate , ierarhia Chomsky (numită uneori Chomsky- Schützenberger ierarhie ) este o clasificare a gramatici formale (și , prin extensie, a respectivelor limbi oficiale generate de gramatici), descris de Noam Chomsky în 1956 .
Ierarhia introdusă de Noam Chomsky se bazează pe modelul gramatical formal . El definește clasele ierarhiei sale ca posibile modele pentru descrierea proprietăților structurale ale limbajelor naturale. Noam Chomsky a propus o clasificare în patru tipuri de limbi, de la tipul 0 la tipul 3. Această terminologie inițială a fost menținută, dar alte nume sunt acum mai frecvente. Chomsky a prezentat aceste familii în termeni de gramatici formale, iar diferitele clase de gramatică sunt definite de restricții succesive sub forma regulilor.
O proprietate remarcabilă a clasificării Chomsky este că, pentru fiecare tip, există o familie de automate care acceptă exact limbi de acest tip. Aceste controlere variază prin natura și utilizarea memoriei auxiliare. Traducerea în clase de complexitate este mai puțin clară: limbaje raționale (tip 3) sunt în DTIME (n), limbaje algebrice (tip 2) în DTIME (n 3 ), limbaje contextuale (tip 1) în DTIME ( n M ), unde M depinde de gramatică, dar inversul nu este adevărat.
Clasificarea lui Chomsky, utilizată în aproape toate manualele de predare a informaticii, sa dovedit a fi foarte fructuoasă în aplicațiile sale, în special în proiectarea și analiza limbajelor de programare și în compilarea acestor limbaje. Limbajele raționale și algebrice au făcut obiectul unor studii teoretice ample în trecut. În limbile sensibile la context sunt utilizate în principal în descrierea limbilor naturale.
Chomsky a definit patru clase de gramatici, denumite de tip 0 la tip 3 și, prin urmare, și patru clase de limbaje, generate de aceste gramatică ierarhic imbricate:
Toate limbile de tip 3 sunt limbi de tip 2. Toate limbile de tip 2 sunt limbi de tip 1. Toate limbile de tip 1 sunt limbi de tip 0. Următorul tabel rezumă corespondența dintre tipurile de gramatică, limbi și mașini.
Gramatică | Reguli de producție | Limba | Mașinărie |
---|---|---|---|
tastați 0 | recursiv enumerabil | Mașină Turing | |
Tipul 1 | contextual | Automat mărginit liniar | |
tipul 2 | algebric | Non-determinist automaton stivă | |
tip 3 | raţional | Automat terminat |
În prezentarea formală de mai jos, este vocabularul gramaticii, compus din simboluri terminale și non-terminale, este setul de simboluri non-terminale și este cuvântul gol.
Nu există restricții cu privire la reguli. Au forma:
Aceste gramatici generează clasa limbajelor recursiv enumerabile . Acestea sunt exact limbile recunoscute de o mașină Turing . Problema dacă un cuvânt aparține unei limbi din această clasă este indecidabilă .
Regulile sunt de forma:
Cu alte cuvinte, orice regulă include un non-terminal înconjurat de două cuvinte care descriu contextul în care variabila poate fi înlocuită. Aceste gramatici sunt numite contextuale (în engleză context-sensitive ), deoarece înlocuirea unui element non-terminal poate depinde de elementele din jurul său: contextul său. Limbajele produse, numite limbaje contextuale sau sensibile la context , sunt exact acelea recunoscute de o mașină Turing nedeterministă cu memorie liniară, denumită în mod obișnuit automate limitate liniar . Există alte formulări echivalente pentru gramaticile care definesc limbaje contextuale.
Regulile sunt de forma:
O astfel de regulă poate fi privită ca o regulă contextuală în care contextul regulilor este gol, cu condiția ca membrul potrivit să nu fie cuvântul gol. Adjectivul „non-contextual” exprimă faptul că simbolurile non-terminale sunt tratate indiferent de locul în care apar. Aceste gramatici generează limbaje algebrice exact , numite și limbaje fără context, limbaje acontextuale sau limbaje non-contextuale. Acestea sunt recunoscute de un automat alimentat cu baterii .
Gramaticile obișnuite sunt fie gramatici liniare la stânga, fie gramatici liniare la dreapta:
Gramaticile obișnuite generează limbaje raționale . Într-adevăr, o gramatică obișnuită se transformă cu ușurință într-un automat finit ( teorema lui Kleene ).
Atenție, nu putem autoriza simultan cele două tipuri de reguli într-o gramatică fără a părăsi clasa limbajelor raționale: obținem gramaticile liniare care constituie o clasă intermediară între tipul 2 și tipul 3. Regulile unei linii gramaticale sunt de forma:
Vezi și exemplele de pe pagina de gramatică formală . Teoria limbajelor formale are multe instrumente pentru a afirma sau a invalida tipul unui limbaj (rațional, algebric etc.). Construcția explicită a unei gramatici care recunoaște o limbă dată nu este întotdeauna ușoară.
Ierarhia inițială a lui Chomsky consta din patru clase. Alte clase sunt adesea intercalate:
Cele gramatici de arbori adiacente definesc o familie între limbi algebrice și limbi sensibile la context. Acestea sunt acceptate de automatele de la bord cu baterie . Aceste gramatici fac parte din gramaticile care permit o mai bună înțelegere a structurii limbajelor naturale, grupate sub denumirea de limbaj ușor sensibil la context (en) .
Există și alte rafinamente, care arată că structura nu este „liniară”: de exemplu, dacă comparăm limbaje liniare și limbaje algebrice deterministe, vedem că aceste familii nu sunt cuprinse nici una, nici în cealaltă.
Ierarhia Chomsky privește doar domeniul calculabilului definit paradigmatic prin ceea ce poate calcula o mașină Turing . Dincolo de aceasta există și alte ierarhii de limbi, inclusiv ierarhia aritmetică .