Gramatică regulată

O gramatică obișnuită , în informatică, este o gramatică formală generativă . Numită și dreapta liniară sau stânga liniară , conform ierarhiei Chomsky este o gramatică de tip 3.

Reamintește

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

La fel ca alte gramatici formale, este o cvadruplă ${\mathcal {G}}=\left\langle N,\Sigma ,P,S\right\rangle$ ${\ displaystyle {\ mathcal {G}} = \ left \ langle N, \ Sigma, P, S \ right \ rangle}$ ${\ mathcal {G}} = \ left \ langle N, \ Sigma, P, S \ right \ rangle$ , in care

$Nu.$ ${\ displaystyle N}$ $Nu.$ sunt simbolurile non-terminale
$\Sigma$ ${\ displaystyle \ Sigma}$ $\ Sigma$ sunt simbolurile terminale
$S\in N$ ${\ displaystyle S \ în N}$ $S \ în N$ axioma menționată este simbolul de început non-terminal.
$P.$ ${\ displaystyle P}$ $P.$ sunt regulile de producție, o relație binară de cardinalitate finită pe $(N\cup \Sigma )^{*}\circ N\circ (N\cup \Sigma )^{*}\times (N\cup \Sigma )^{*}$ ${\ displaystyle (N \ cup \ Sigma) ^ {*} \ circ N \ circ (N \ cup \ Sigma) ^ {*} \ times (N \ cup \ Sigma) ^ {*}}$ $(N \ cup \ Sigma) ^ {*} \ circ N \ circ (N \ cup \ Sigma) ^ {*} \ times (N \ cup \ Sigma) ^ {*}$ , pe care în mod normal scriem ca $\alpha \to \beta$ ${\ displaystyle \ alpha \ to \ beta}$ $\ alpha \ to \ beta$
această scriere ne spune că în stânga trebuie să existe cel puțin un non-terminal și în dreapta orice.

Definiție

Producțiile unei gramatici obișnuite sunt de tipul:

în cazul stânga liniară (în engleză left grammar regular )

A\to \beta ,A\in N,\beta \in (N\circ \Sigma )\cup \Sigma

{\ displaystyle A \ to \ beta, A \ in N, \ beta \ in (N \ circ \ Sigma) \ cup \ Sigma}

{\ displaystyle A \ to \ beta, A \ in N, \ beta \ in (N \ circ \ Sigma) \ cup \ Sigma}

adică în stânga regulii de producție există un non-terminal și în dreapta un non-terminal urmat de un terminal sau un singur terminal.

în cazul drepturilor liniare (în engleză right regular grammar )

A\to \beta ,A\in N,\beta \in (\Sigma \circ N)\cup \Sigma

{\ displaystyle A \ to \ beta, A \ in N, \ beta \ in (\ Sigma \ circ N) \ cup \ Sigma}

{\ displaystyle A \ to \ beta, A \ in N, \ beta \ in (\ Sigma \ circ N) \ cup \ Sigma}

adică în stânga regulii de producție există un non-terminal și în dreapta un terminal urmat de un non-terminal sau un singur terminal.

Acordăm atenție faptului că nu trebuie să existe producții mixte formate din dreapta și stânga liniare în același timp în aceeași gramatică, deoarece în acest caz nu mai suntem în prezența unei gramatici obișnuite, ci a unei gramatici libere de context ( nu contextual ) așa cum este evidențiat într-un exemplu de mai jos.

Acestea sunt numite regulate deoarece limbajele generate de aceste gramatici sunt reprezentabile prin expresii regulate .
Termenul liniar derivă din faptul că în dreapta producțiilor putem găsi cel mult un non-terminal; stânga sau dreapta indică locul în care non-terminalul va fi relativ la terminal.

Limbile care pot fi generate de gramaticile obișnuite (tip-3) se numesc limbi regulate și sunt echivalente cu limbile recunoscute de automatele de stare finită și cu limbile reprezentate de expresii regulate .

Fiecare gramatică obișnuită este, de asemenea, o gramatică fără context, deoarece gramaticile de tip 3 sunt strict cuprinse în gramaticile de tip 2 conform ierarhiei Chomsky .

Unele manuale și articole nu permit reguli de producție goale ( ε-producții ) și presupun că șirul gol nu este prezent în limbă.
În orice caz, se dovedește teorema care garantează că o gramatică dată ${\mathcal {G}}$ ${\ displaystyle {\ mathcal {G}}}$ ${\ mathcal {G}}$ ale cărei reguli de producție P pot fi separate în două subseturi care conțin una producțiile goale și cealaltă producțiile obișnuite, atunci există o gramatică regulată ${\mathcal {G}}'$ ${\ displaystyle {\ mathcal {G}} '}$ ${\ displaystyle {\ mathcal {G}} '}$ format din gramatică ${\mathcal {G}}$ ${\ displaystyle {\ mathcal {G}}}$ ${\ mathcal {G}}$ la care au fost eliminate producțiile goale.
Mai formal ${\mathcal {G}}'$ ${\ displaystyle {\ mathcal {G}} '}$ ${\ displaystyle {\ mathcal {G}} '}$ regulat fără ε-producții astfel încât $L({\mathcal {G}}')=L({\mathcal {G}})-\{\varepsilon \}$ ${\ displaystyle L ({\ mathcal {G}} ') = L ({\ mathcal {G}}) - \ {\ varepsilon \}}$ ${\ displaystyle L ({\ mathcal {G}} ') = L ({\ mathcal {G}}) - \ {\ varepsilon \}}$

Exemple

Un exemplu de gramatică liniară dreaptă ${\mathcal {G}}$ ${\ displaystyle {\ mathcal {G}}}$ ${\ mathcal {G}}$ cu $N=\{S\},\Sigma =\{a,b\},S$ ${\ displaystyle N = \ {S \}, \ Sigma = \ {a, b \}, S}$ ${\ displaystyle N = \ {S \}, \ Sigma = \ {a, b \}, S}$ axiomă, $P.$ ${\ displaystyle P}$ $P.$ format din următoarele reguli de producție:

S\to aS

{\ displaystyle S \ to aS}

{\ displaystyle S \ to aS}

S\to b

{\ displaystyle S \ to b}

{\ displaystyle S \ to b}

Această gramatică descrie același limbaj ca și expresia regulată $a^{*}b$ ${\ displaystyle a ^ {*} b}$ ${\ displaystyle a ^ {*} b}$ .

Un alt exemplu de gramatică liniară dreaptă ${\mathcal {G}}$ ${\ displaystyle {\ mathcal {G}}}$ ${\ mathcal {G}}$ cu $N=\{S,C\},\Sigma =\{a,b,c\},S$ ${\ displaystyle N = \ {S, C \}, \ Sigma = \ {a, b, c \}, S}$ ${\ displaystyle N = \ {S, C \}, \ Sigma = \ {a, b, c \}, S}$ axiomă, $P.$ ${\ displaystyle P}$ $P.$ format din următoarele reguli de producție:

S\to aS

{\ displaystyle S \ to aS}

{\ displaystyle S \ to aS}

S\to bC

{\ displaystyle S \ to bC}

{\ displaystyle S \ to bC}

S\to b

{\ displaystyle S \ to b}

{\ displaystyle S \ to b}

C\to cC

{\ displaystyle C \ to cC}

{\ displaystyle C \ to cC}

C\to c

{\ displaystyle C \ to c}

{\ displaystyle C \ to c}

Această gramatică descrie același limbaj ca și expresia regulată $a*bc*$ ${\ displaystyle a * bc *}$ ${\ displaystyle a * bc *}$ .

Exemplu de gramatică neregulată

O gramatică care generează limbaj $L=\{a^{i}b^{i}\;|\;i\geq 0\}$ ${\ displaystyle L = \ {a ^ {i} b ^ {i} \; | \; i \ geq 0 \}}$ ${\ displaystyle L = \ {a ^ {i} b ^ {i} \; | \; i \ geq 0 \}}$ ar putea fi ${\mathcal {G}}$ ${\ displaystyle {\ mathcal {G}}}$ ${\ mathcal {G}}$ cu $N=\{S,A\},\Sigma =\{a,b\},S$ ${\ displaystyle N = \ {S, A \}, \ Sigma = \ {a, b \}, S}$ ${\ displaystyle N = \ {S, A \}, \ Sigma = \ {a, b \}, S}$ axiomă, $P.$ ${\ displaystyle P}$ $P.$ format din următoarele reguli de producție:

S\to aA

{\ displaystyle S \ to aA}

S \ to aA

A\to Sb

{\ displaystyle A \ to Sb}

{\ displaystyle A \ to Sb}

S\to \varepsilon

{\ displaystyle S \ to \ varepsilon}

S \ to \ varepsilon

dar aceasta nu este o gramatică obișnuită, ci o gramatică fără context ; are atât producții din dreapta, cât și din stânga și, prin urmare, nu este obișnuit.

Bibliografie

Giorgio Ausiello, Fabrizio d'Amore, Giorgio Gambosi. Limbi, modele, complexitate . Franco Angeli Editore, 2003 ISBN 88-464-4470-1

Elemente conexe

Gramatica liniară și limbajul liniar

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.

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