Gramàtica regular

En lingüística i informàtica, una gramàtica regular és una gramàtica formal en que pot ser classificada com regular-dreta o regular-esquerra. Cada gramàtica regular defineix un llenguatge regular.

Definició

Una gramàtica regular dreta una gramàtica formal (N, Σしぐま, P, S) tal que totes les regles de producció a P son d'alguna de les següents formes:

1. A → a - on A és un no-terminal a N i a és un terminal a Σしぐま
2. A → aB - on A i B son no-terminal a N i a és a Σしぐま
3. A → εいぷしろん - on A és a N i εいぷしろん denotes la cadena buida (cadena de longitud 0)

Una gramàtica regular esquerra es defineix de la següent forma:

1. A → a - on A és un no-terminal a N i a és un terminal a Σしぐま
2. A → Ba - on A i B son no-terminal a N i a és a Σしぐま
3. A → εいぷしろん - on A és a N i εいぷしろん denotes la cadena buida (cadena de longitud 0)

Una gramàtica regular és o bé una gramàtica d'esquerra o bé de dreta.

Si es barregen regles de dretes amb d'esquerres s'obté una gramàtica lineal, però no necessàriament una gramàtica regular.