Gramática regular

Gramática regular

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:

  1. Aa, donde A es un símbolo no-terminal en N y a uno terminal en Σ
  2. AaB, donde A y B pertenecen a N y a pertenece a Σ
  3. A → ε, donde A pertenece a N.

Análogamente, en una gramática regular izquierda, las reglas son de la siguiente forma:

  1. Aa, donde A es un símbolo no-terminal en N y a uno terminal en Σ
  2. ABa, donde A y B pertenecen a N y a pertenece a Σ
  3. A → ε, donde A pertenece a N.


Una definición equivalente evita la regla 1 (Aa) ya que es sustituible por:

AaL
L → ε

en el caso de las gramáticas regulares derechas y por:

ALa
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.


Véase también


Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Gramática 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… …   Enciclopedia Universal

  • Gramática generativa transformacional — Gramática transformacional es una expresión que designa al tipo de gramática generativa que utiliza reglas transformacionales u otros mecanismos para representar el desplazamiento de constituyentes y otros fenómenos del lenguaje natural. En… …   Wikipedia Español

  • regular — verbo transitivo 1. Poner (una persona) [una cosa] en orden o en estado de normalidad: Un guardia regula la circulación del cruce. Sinónimo: organizar. 2. Determinar ( …   Diccionario Salamanca de la Lengua Española

  • Gramática cultural — es el término que utiliza la Guerrilla de la comunicación para referirse a todo el marco de reglas y de convenciones que regulan las interacciones y relaciones sociales, las representaciones de objetos y espacios, y el transcurso normal de las… …   Wikipedia Español

  • Gramática del pipil — «Gramática del náhuat» redirige aquí. Para otras acepciones, véase Gramática del náhuat (desambiguación). Gramática pipil se refiere al conjunto de reglas y principios que regulan el uso del idioma pipil. Este artículo muestra un esquema… …   Wikipedia Español

  • Gramática pipil — Saltar a navegación, búsqueda Con Gramática pipil se refiere al conjunto de reglas y princios que regulan el uso del idioma pipil. Este artículo muestra un esquema gramatical del idioma náhuat o pipil, una lengua perteneciente a la familia… …   Wikipedia Español

  • regular — adj. 2 g. 1. Conforme às regras ou leis. = NORMAL ≠ ANORMAL, IRREGULAR 2. Que segue as leis, as regras ou os costumes. ≠ ILEGAL, IRREGULAR 3. Bem proporcionado. = HARMONIOSO ≠ DESARMONIOSO, DESPROPORCIONAL, IRREGULAR 4. Exato, pontual. 5. Nem… …   Dicionário da Língua Portuguesa

  • Gramática del español — Estatua del gramático Antonio de Nebrija en la Biblioteca Nacional de Madrid, por Anselmo Nogués. En 1492, Nebrija fue el primer europeo en escribir una gramática de una lengua románica o neolatina, el español …   Wikipedia Español

  • Gramática libre de contexto — En lingüística e informática, una gramática libre de contexto (o de contexto libre) es una gramática formal en la que cada regla de producción es de la forma: V → w Donde V es un símbolo no terminal y w es una cadena de terminales y/o no… …   Wikipedia Español

  • Gramática (autómata) — Una gramática ( G ) desde el punto de vista de la teoría de autómatas es un conjunto finito de reglas que describen toda la secuencia de símbolos pertenecientes a un lenguaje específico L. Dos gramáticas que describan el mismo lenguaje se llaman… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”