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:
A → a - on A és un no-terminal a N i a és un terminal a Σ A → aB - on A i B son no-terminal a N i a és a Σ 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:
A → a - on A és un no-terminal a N i a és un terminal a Σ A → Ba - on A i B son no-terminal a N i a és a Σ 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.
Referències
Categoria:Complexitat computacional Categoria:Llenguatges formals