En informática una gramática regular es una gramática formal (N, Σ, P, S) que puede ser clasificada como regular izquierda o regular 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.
Una gramática regular derecha es aquella 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.
Análogamente, en una gramática regular izquierda, las reglas son de la siguiente forma:
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.
Una definición equivalente evita la regla 1 (A → a) ya que es sustituible por:
A → aL
L → ε
en el caso de las gramáticas regulares derechas y por:
A → La
L → ε
en el caso de las izquierdas.
Algunos autores alternativamente no permiten el uso de la regla 3 suponiendo que la cadena vacía no pertenece al lenguaje.
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 izquierda es posible convertirla, mediante un algoritmo en una derecha y viceversa.
gramática, regular, informática, gramática, regular, gramática, formal, puede, clasificada, como, regular, izquierda, regular, derecha, gramáticas, regulares, sólo, pueden, generar, lenguajes, regulares, manera, similar, autómatas, finitos, expresiones, regula. En informatica una gramatica regular es una gramatica formal N S P S que puede ser clasificada como regular izquierda o regular derecha Las gramaticas regulares solo pueden generar a los lenguajes regulares de manera similar a los automatas finitos y las expresiones regulares Dos gramaticas regulares que generan el mismo lenguaje regular se denominan equivalentes Toda gramatica regular es una gramatica libre de contexto Una gramatica regular derecha es aquella cuyas reglas de produccion P son de la siguiente forma A a donde A es un simbolo no terminal en N y a uno terminal en S A aB donde A y B pertenecen a N y a pertenece a S A e donde A pertenece a N Analogamente en una gramatica regular izquierda las reglas son de la siguiente forma A a donde A es un simbolo no terminal en N y a uno terminal en S A Ba donde A y B pertenecen a N y a pertenece a S A e donde A pertenece a N Una definicion equivalente evita la regla 1 A a ya que es sustituible por A aL L een el caso de las gramaticas regulares derechas y por A La L een el caso de las izquierdas Algunos autores alternativamente no permiten el uso de la regla 3 suponiendo que la cadena vacia no pertenece al lenguaje Un ejemplo de una gramatica regular G con N S A S a b c P se define mediante las siguientes reglas S aS S bA A e A cAdonde S es el simbolo inicial Esta gramatica describe el mismo lenguaje expresado mediante la expresion regular a bc Dada una gramatica regular izquierda es posible convertirla mediante un algoritmo en una derecha y viceversa Vease tambien EditarGramatica formal Jerarquia de Chomsky Datos Q645527 Obtenido de https es wikipedia org w index php title Gramatica regular amp oldid 117376892, wikipedia, wiki, leyendo, leer, libro, biblioteca,
