Gramática regular
Keywords: Gramática regular, Autómata finito, Expresión regular, Gramática formal, Gramática libre de contexto, Informática, Jerarquía de Chomsky, Lenguaje regular
En informática una gramática regular es una gramática formal (N, Σ, P, S) y puede ser clasificada en regular izquierda o derecha. Las gramáticas regulares sólo pueden generar a los lenguajes regulares de manera similar a los autómatas finitos y las expresiones regulares.
Dos gramáticas regulares que generan el mismo lenguaje regular se denominan equivalentes. Toda gramática regular es una gramática libre de contexto.
En una gramática regular derecha cuyas reglas de producción P son de la siguiente forma:
- A → a donde A es un símbolo no-terminal en N y a uno terminal en Σ
- A → aB donde A y B pertenecen a N y a pertenece a Σ
- A → ε donde A pertenece a N.
En una gramática regular izquierda, las reglas son las siguientes:
- A → a donde A es un símbolo no-terminal en N y a uno terminal en Σ
- A → Ba donde A y B pertenecen a N y a pertenece a Σ
- A → ε donde A pertenece a N.
Un ejemplo de una gramática regular G con N = {S, A}, Σ = {a, b, c}, P se define mediante las siguientes reglas:
- S → aS
- S → bA
- A → ε
- A → cA
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 derecha es posible convertirla, mediante un algoritmo en una derecha y viceversa.
Véase también: Gramática formal, Jerarquía de Chomsky
categoría:Lenguajes formales