Gramatica obișnuită

O gramatică obișnuită  este o gramatică formală de tip 3 în ierarhia Chomsky , gramaticile regulate definesc exact toate limbajele regulate și, prin urmare, sunt echivalente cu mașinile de stări și cu expresiile regulate . Gramaticile obișnuite sunt un subset al gramaticilor fără context .

Stabilirea unui set de reguli

O gramatică obișnuită poate fi specificată printr-un set de reguli ca o gramatică normală stânga sau dreapta.

Gramatica obișnuită dreaptă sau gramatică liniară dreapta - toate regulile pot fi în una dintre următoarele forme:

1. A → a
2. A → aB
3. A →ε

gramatică obișnuită stângă sau gramatică liniară stângă - toate regulile pot fi în una dintre următoarele forme:

1. A → a
2. A → Ba
3. A →ε

Unde

• literele majuscule ( A , B ) denotă non-terminale din mulțimea N
• literele mici ( a , b ) indică terminale din mulțimea Σ
• ε este un șir gol, adică un șir de lungime 0

Clasele de gramatici regulate dreapta și stânga sunt echivalente - fiecare luată separat este suficientă pentru a defini toate limbajele obișnuite. Orice gramatică obișnuită poate fi convertită de la stânga la dreapta și invers.

Denumirile alternative se datorează faptului că sunt subclase ale clasei mai generale de gramatici liniare .

Exemplu

Gramatica regulată dreaptă G dată de N = {S, A}, Σ = {a, b, c}, P constă din următoarele reguli:

iar S este simbolul de început. Această gramatică descrie aceeași limbă ca și expresia regulată a*bc*.

Limitat

Este esențial ca regulile să fie fie doar stânga-regulate, fie doar dreapta-regulate. Nu este permisă o combinație a ambelor. De exemplu, un limbaj cu șiruri fără context de forma , unde nu este regulat, dar este dat de o gramatică G , unde N = {S, A}, Σ = {a, b}, P constă din

iar S este simbolul de început. Această gramatică conține atât reguli stânga-regular, cât și dreapta-regular și, prin urmare, nu este obișnuită.

Vezi și

• Expresii regulate - în teoria limbajelor formale
• Prefix gramatica

Literatură

• Robin Hunter. Concepte de bază ale compilatorului = Esența compilatorilor. - M . : „Williams” , 2002. - S. 256. - ISBN 5-8459-0360-2 .
• Serebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Teoria și implementarea limbajelor de programare  - M.: MZ-Press, 2006, ed. a 2-a. — ISBN 5-94073-094-9