Gramatica sintagmatică

Gramatica sintagmatică , cunoscută și sub numele de ierarhia Chomsky , este o ierarhie conținând clase de gramatică formală care generează limbaje formale . Această ierarhie a gramaticilor, numite și gramatici sintagmatice , a fost descrisă de Noam Chomsky .

Gramatici formale

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

O gramatică formală constă dintr-o selecție finită a simbolurilor terminale (literele cuvintelor într-un limbaj formal), o selecție de simboluri non-terminale , o selecție finită a regulilor de producție cu o porțiune dreaptă și o stânga constând dintr-un cuvânt al acestor simboluri și un simbol de pornire . O regulă ar putea fi aplicată unui cuvânt înlocuind partea stângă cu partea dreaptă. O derivare este o secvență de aplicații de regulă. O astfel de gramatică definește limbajul formal al tuturor cuvintelor constând doar din simboluri terminale la care se poate ajunge printr-o derivare a simbolului de pornire.

Simbolurile non-terminale sunt de obicei reprezentate de literele primelor locuri, cele terminale de literele ultimului și simbolul începând de la $S.$ ${\ displaystyle S}$ $S.$ . De exemplu, gramatica cu simboluri terminale $\{a,b\}$ ${\ displaystyle \ {a, b \}}$ $\ {a, b \}$ , nu terminale $\{S,A,B\}$ ${\ displaystyle \ {S, A, B \}}$ $\ {S, A, B \}$ poate avea ca reguli de producție:

S.

{\ displaystyle S}

S.

→

LA B. S.

{\ displaystyle ABS}

{\ displaystyle ABS}

S.

{\ displaystyle S}

S.

→ ε (unde ε este șirul gol)

B. LA

{\ displaystyle BA}

BA

→

LA B.

{\ displaystyle AB}

AB

B. S.

{\ displaystyle BS}

{\ displaystyle BS}

→

b

{\ displaystyle b}

b

B. b

{\ displaystyle Bb}

{\ displaystyle Bb}

→

b b

{\ displaystyle bb}

{\ displaystyle bb}

LA b

{\ displaystyle Ab}

{\ displaystyle Ab}

→

la b

{\ displaystyle ab}

ab

LA la

{\ displaystyle Aa}

{\ displaystyle Aa}

→

la la

{\ displaystyle aa}

{\ displaystyle aa}

și simbolul de început $S.$ ${\ displaystyle S}$ $S.$ definește limbajul tuturor cuvintelor pe care le formează $a^{n}b^{n}$ ${\ displaystyle a ^ {n} b ^ {n}}$ $a ^ {n} b ^ {n}$ (de exemplu $n$ ${\ displaystyle n}$ $n$ copii ale $b$ ${\ displaystyle b}$ $b$ ). Următorul este o gramatică mai simplă care definește un limbaj similar: Terminale $\{p,q\}$ ${\ displaystyle \ {p, q \}}$ $\ {p, q \}$ , nonterminali $\{S\}$ ${\ displaystyle \ {S \}}$ $\ {S \}$ , simbol al plecării $S.$ ${\ displaystyle S}$ $S.$ , reguli de producție

S.

{\ displaystyle S}

S.

→

p S. q

{\ displaystyle pSq}

{\ displaystyle pSq}

S.

{\ displaystyle S}

S.

→ ε

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