Gramática regular

Una gramática regular  es una gramática formal de tipo 3 en la jerarquía de Chomsky , las gramáticas regulares definen exactamente todos los lenguajes regulares y, por lo tanto, son equivalentes a máquinas de estado y expresiones regulares . Las gramáticas regulares son un subconjunto de las gramáticas libres de contexto .

Establecer un conjunto de reglas

Una gramática regular se puede especificar mediante un conjunto de reglas como una gramática regular izquierda o derecha.

Gramática regular derecha o gramática lineal derecha : todas las reglas pueden tener una de las siguientes formas:

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

gramática regular izquierda , o gramática lineal izquierda , - todas las reglas pueden estar en una de las siguientes formas:

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

dónde

• las letras mayúsculas ( A , B ) denotan no terminales del conjunto N
• las letras minúsculas ( a , b ) denotan terminales del conjunto Σ
• ε es una cadena vacía, es decir, una cadena de longitud 0

Las clases de gramáticas regulares derecha e izquierda son equivalentes: cada una tomada por separado es suficiente para definir todos los lenguajes regulares. Cualquier gramática regular se puede convertir de izquierda a derecha y viceversa.

Los nombres alternativos se deben al hecho de que son subclases de la clase más general de gramáticas lineales .

Ejemplo

La gramática regular derecha G dada por N = {S, A}, Σ = {a, b, c}, P consta de las siguientes reglas:

y S es el símbolo de inicio. Esta gramática describe el mismo lenguaje que la expresión regular a*bc*.

Limitado

Es esencial que las reglas sean solo regulares de izquierda o regulares de derecha. No se permite una combinación de ambos. Por ejemplo, un lenguaje de cadenas libre de contexto de la forma , donde no es regular, pero está dado por una gramática G , donde N = {S, A}, Σ = {a, b}, P consta de

y S es el símbolo de inicio. Esta gramática contiene reglas regulares a la izquierda y regulares a la derecha y, por lo tanto, no es regular.

Véase también

• Expresiones regulares - en la teoría de los lenguajes formales
• Gramática de prefijos

Literatura

• Cazador de petirrojos. Conceptos básicos del compilador = La esencia de los compiladores. - M .: "Williams" , 2002. - S. 256. - ISBN 5-8459-0360-2 .
• Serebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Teoría e implementación de lenguajes de programación  - M.: MZ-Press, 2006, 2ª ed. — ISBN 5-94073-094-9