Gramática regular

Dos gramáticas regulares que generan el mismo lenguaje regular se denominan equivalentes.Una definición equivalente evita la regla 1 (A → a) ya que es sustituible por: en el caso de las gramáticas regulares derechas y por: en el caso de las izquierdas.Un ejemplo de una gramática regular G con N = {S, A}, Σ = {a, b, c}, P se define mediante las siguientes reglas: donde S es el símbolo inicial.Esta gramática describe el mismo lenguaje expresado mediante la expresión regular a*bc*.Dada una gramática regular izquierda es posible convertirla, mediante un algoritmo en una derecha y viceversa.