Ierarhia Chomsky

Ierarhia Chomsky este un set de clase formale de gramatică care generează limbaje formale . Ierarhia acestor gramatici, numită și gramatica structurii frazelor , a fost descrisă de Noam Chomsky în 1956 ^[1] ^[2] .

Gramatici formale

Același subiect în detaliu: Gramatica formală .

O gramatică formală $G.$ ${\ displaystyle G}$ $G.$ este o cvadruplă $G=(N,T,S,P)$ ${\ displaystyle G = (N, T, S, P)}$ $G = (N, T, S, P)$ , Unde $Nu.$ ${\ displaystyle N}$ $Nu.$ este un set finit și ne-gol de simboluri numit alfabet non-terminal , $T.$ ${\ displaystyle T}$ $T.$ este un set finit și ne-gol de simboluri numit alfabet terminal (literele unui cuvânt în limbaj formal), $P.$ ${\ displaystyle P}$ $P.$ este o relație binară de cardinalitate finită, cu alte cuvinte un set de reguli de producție (cu partea stângă și partea dreaptă) și, în final, $S.$ ${\ displaystyle S}$ $S.$ aparținând $Nu.$ ${\ displaystyle N}$ $Nu.$ se numește Axiomă și reprezintă simbolul de început non-terminal ( simbol inițial non-terminal). O regulă de producție poate fi aplicată unui cuvânt înlocuind partea stângă cu partea dreaptă. O derivare este o succesiune de aplicații ale regulilor de producție. În acest fel, o gramatică definește un limbaj formal cu toate cuvintele constând doar din simboluri terminale la care se poate ajunge de la simbolul inițial prin derivări.

Simbolurile non-terminale sunt în general reprezentate prin litere mari, terminale cu litere mici, iar simbolul inițial cu $S.$ ${\ displaystyle S}$ $S.$ . De exemplu, gramatica cu simboluri terminale $\{a,b\}$ ${\ displaystyle \ {a, b \}}$ $\ {a, b \}$ , și simboluri non-terminale $\{S,A,B\}$ ${\ displaystyle \ {S, A, B \}}$ $\ {S, A, B \}$ , și reguli de producție

S\to ABS

{\ displaystyle S \ to ABS}

S \ la ABS

S\to \varepsilon

{\ displaystyle S \ to \ varepsilon}

S \ to \ varepsilon

(unde este

\varepsilon

{\ displaystyle \ varepsilon}

\ varepsilon

este șirul gol)

BA\to AB

{\ displaystyle BA \ to AB}

BA \ to AB

BS\to b

{\ displaystyle BS \ to b}

BS \ to b

Bb\to bb

{\ displaystyle Bb \ to bb}

Bb \ to bb

Ab\to ab

{\ displaystyle Ab \ to ab}

Ab \ to ab

Aa\to aa

{\ displaystyle Aa \ to aa}

Aa \ to aa

și simbolul inițial $S.$ ${\ displaystyle S}$ $S.$ , definește limbajul compus din toate cuvintele din formă $a^{n}b^{n}$ ${\ displaystyle a ^ {n} b ^ {n}}$ $a ^ {n} b ^ {n}$ (Adică toate șirurile formate din $n$ ${\ displaystyle n}$ $n$ repetări de $la$ ${\ displaystyle a}$ $la$ urmată de $n$ ${\ displaystyle n}$ $n$ repetări de $b$ ${\ displaystyle b}$ $b$ , De exemplu $la la la b b b$ ${\ displaystyle aaabbb}$ $aaabbb$ pentru $n=3$ ${\ displaystyle n = 3}$ $n = 3$ sau $la la la la la b b b b b$ ${\ displaystyle aaaaabbbbb}$ $aaaaabbbbb$ pentru $n=5$ ${\ displaystyle n = 5}$ $n = 5$ ).

Următorul este o gramatică simplă care definește un limbaj similar: simboluri terminale $\{p,q\}$ ${\ displaystyle \ {p, q \}}$ $\ {p, q \}$ , simboluri non-terminale $\{S\}$ ${\ displaystyle \ {S \}}$ $\ {S \}$ , simbol inițial $S.$ ${\ displaystyle S}$ $S.$ , reguli de producție

S\to pSq

{\ displaystyle S \ to pSq}

S \ to pSq

S\to \varepsilon

{\ displaystyle S \ to \ varepsilon}

S \ to \ varepsilon

Ierarhia

Ierarhia Chomsky constă din următoarele niveluri:

Gramaticele de tip 0 (gramatici nelimitate) includ toate gramaticile formale. Aceste gramatici au reguli de formă $\alpha A\beta \rightarrow \alpha \gamma \beta$ ${\ displaystyle \ alpha A \ beta \ rightarrow \ alpha \ gamma \ beta}$ $\ alpha A \ beta \ rightarrow \ alpha \ gamma \ beta$ cu $LA$ ${\ displaystyle A}$ $LA$ simbol non-terminal, $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ , $\beta$ ${\ displaystyle \ beta}$ $\ beta$ Și $\gamma$ ${\ displaystyle \ gamma}$ $\gamă$ șiruri de simboluri terminale și non-terminale. Aceste gramatici admit și derivări care scad lungimea propoziției, de exemplu producțiile ε, deci $\gamma$ ${\ displaystyle \ gamma}$ $\gamă$ poate fi gol. Aceste gramatici generează exact toate limbile care pot fi acceptate de o mașină Turing . Aceste limbi sunt, de asemenea, cunoscute ca limbi recursiv enumerabile . Rețineți că aceste limbi sunt diferite de limbile recursive care pot fi recunoscute de o mașină Turing care se termină mereu . Limbile de tip 0 sunt semidecidabile în conformitate cu Turing (dat fiind un limbaj de tip 0 L este întotdeauna posibil să se definească un MT ℳ astfel încât, dacă un șir s $\in$ ${\ displaystyle \ in}$ $\în$ L atunci ℳ încheie calculul acceptând s , dacă în schimb s $\not \in$ ${\ displaystyle \ not \ in}$ $\ nu în$ L ℳ nu poate termina calculul lui s ).

Gramaticile de tip 1 ( gramatici dependente de context ) generează limbaje dependente de context . Aceste gramatici au reguli de formă $\alpha A\beta \rightarrow \alpha \gamma \beta$ ${\ displaystyle \ alpha A \ beta \ rightarrow \ alpha \ gamma \ beta}$ $\ alpha A \ beta \ rightarrow \ alpha \ gamma \ beta$ cu $LA$ ${\ displaystyle A}$ $LA$ simbol non-terminal e $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ , $\beta$ ${\ displaystyle \ beta}$ $\ beta$ Și $\gamma$ ${\ displaystyle \ gamma}$ $\gamă$ șiruri de simboluri terminale și non-terminale (orice regulă de producție care reduce lungimea șirurilor nu este permisă). Corzile $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ Și $\beta$ ${\ displaystyle \ beta}$ $\ beta$ pot fi goale, dar $\gamma$ ${\ displaystyle \ gamma}$ $\gamă$ trebuie să fie ne-gol. Limbile descrise de aceste gramatici sunt exact toate limbile care pot fi recunoscute de o mașinărie Turing nedeterministă în care banda este limitată de un număr constant de ori de lungimea intrării.

Gramaticile de tip 2 ( gramatici fără context ) generează limbaje fără context . Aceste gramatici sunt definite de reguli în formă $A\rightarrow \gamma$ ${\ displaystyle A \ rightarrow \ gamma}$ $A \ rightarrow \ gamma$ cu $LA$ ${\ displaystyle A}$ $LA$ simbol non-terminal e $\gamma$ ${\ displaystyle \ gamma}$ $\gamă$ un șir de simboluri terminale și non-terminale. Aceste limbi sunt exact toate limbile care pot fi recunoscute de un automat nedeterminist în stivă . Limbajele fără context sunt teoretic baza sintaxei multor limbaje de programare ( Analiza sintactică ).

Gramaticile de tip 3 ( gramatici obișnuite ) generează limbaje obișnuite . Acest tip de gramatică își restricționează regulile la un singur simbol non-terminal pe partea stângă a ieșirii și pe partea dreaptă un singur simbol terminal, care poate fi urmat (sau precedat, dar nu ambele forme în aceeași gramatică) de un simbol unic non-terminal. Regula $S\to \varepsilon$ ${\ displaystyle S \ to \ varepsilon}$ $S \ to \ varepsilon$ totuși este permisă aici $S.$ ${\ displaystyle S}$ $S.$ nu apare în partea dreaptă a regulilor de producție. Aceste limbi sunt exact toate limbile recunoscute de un automat cu stare finită . În plus, această familie de limbaje formale poate fi obținută cu expresii regulate . Limbajele obișnuite sunt utilizate în mod obișnuit pentru a defini tiparele de căutare și structura lexicală a limbajelor de programare ( Analiza lexicală ).

Rețineți că setul de gramatici corespunzătoare limbajelor recursive nu este membru al acestei ierarhii.

Gramatica de tip 0 este singura care poate genera șirul gol. Puteți extinde gramaticile de tip 1, 2 și 3, astfel încât să poată genera același limbaj îmbogățit ca șirul gol. Regula producției $S\rightarrow \varepsilon$ ${\ displaystyle S \ rightarrow \ varepsilon}$ $S \ rightarrow \ varepsilon$ este permis dacă $S.$ ${\ displaystyle S}$ $S.$ nu apare în partea dreaptă a regulilor de producție. Introducerea producțiilor ε are consecințe diferite în funcție de tipul de gramatică. În cazul gramaticilor de tip 2 sau 3, producțiile ε nu măresc puterea expresivă a gramaticii. În schimb, gramaticile de tip 1 sunt transformate în gramatice de tip 0, adică crește puterea expresivă a gramaticii.

Fiecare limbaj obișnuit este lipsit de context, fiecare limbaj fără context depinde de context (este de fapt un caz special în care șirurile $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ Și $\beta$ ${\ displaystyle \ beta}$ $\ beta$ sunt neapărat goale) și fiecare limbaj dependent de context este recursiv, iar în cele din urmă fiecare limbaj recursiv este recursiv enumerabil. Acestea sunt incluziuni proprii, în sensul că există limbaje recursive enumerabile care sunt limbaje non-recursive, recursive care nu sunt dependente de context, limbaje dependente de context care nu sunt contextuale și context -limbi gratuite care nu sunt obișnuite.

Notă

^ Noam Chomsky: Trei modele pentru descrierea limbajului , IRE Transactions on Information Theory, 2 (1956), paginile 113-124
^ Noam Chomsky: Despre anumite proprietăți formale ale gramaticilor , Information and Control, 1 (1959), paginile 91-112

Elemente conexe

linkuri externe

( EN ) lecture5 , pe web.archive.org , 5 aprilie 2014. Accesat la 14 aprilie 2020 (arhivat din original la 5 aprilie 2014) .

Teoria automatelor : limbaje formale și gramatici formale
Ierarhia Chomsky	Gramatica formală	Limba	Automat minim
Tipul-0	(nelimitat)	Recursiv enumerabil	Mașină Turing
	(nelimitat)	Recursiv	Decider
Tipul 1	Context dependent	Context dependent	Automat liniar
Tipul 2	Fără context	Fără context	Automat cu baterie ND
Tipul 3	Regulat	Regulat	Stări finite
Fiecare categorie de limbă sau gramatică este un subset adecvat al categoriei imediat deasupra acesteia.

Controlul autorității	GND ( DE ) 4529323-5

Portalul lingvistic : accesați intrările Wikipedia care se ocupă de lingvistică

[1] Noam Chomsky: Trei modele pentru descrierea limbajului , IRE Transactions on Information Theory, 2 (1956), paginile 113-124

[2] Noam Chomsky: Despre anumite proprietăți formale ale gramaticilor , Information and Control, 1 (1959), paginile 91-112

[1]

[2]