gramatica regulată

Stabilirea setului de reguli

gramatica regulată poate fi definită printr-un set de reguli ca gramatica regulată stânga sau la dreapta.

gramatica regulată dreapta - toate regulile pot fi într-una din următoarele forme:

gramatica regulată stânga - toate regulile pot fi într-una din următoarele forme:

• capace (A. B) denota non-terminale ale multitudinii de N
• litere mici (a. b) denotă bornele pluralității Σ
• ε - string gol, adică Lungimea liniei 0

Clasele de dreapta și la stânga Gramatici regulate sunt echivalente - suficiente pentru a defini în mod individual toate limbile obișnuite. Orice gramatica regulată poate fi convertit de la stânga la dreapta și invers.

Dreptul gramatica regulată G. predeterminate N =, Σ =, P este alcătuit din următoarele reguli:

S → aS S → bA A → ε A → cA

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

Orice gramatica de context poate fi ușor transformată într-o formă în care sunt regulile numai din stânga-dreapta regulată și-regulat (pentru gramatici independente de context este permisă prezența ambele în același timp). Prin urmare, astfel de gramatici poate exprima toate limbile de context. Gramatici regulate pot conține fie o reguli-stânga regulat, sau de dreapta regulat, dar nu ambele simultan. Prin urmare, ei pot descrie doar un subset de limbi numite limbaje regulate.

De exemplu, un context liber siruri de limbaj de forma a i b i. i≥0 gramatica definită G. unde N =, Σ =, P constă din reguli

S → aA A → D S → ε

și S este simbolul de pornire. Rețineți că această gramatica conține atât reguli stânga-dreapta regulate și-regulate, și, prin urmare, nu este regulat.