Scribd
Cargar
531 vistas2 páginas

Introducción a Gramáticas Regulares

Una gramática regular es una gramática formal que puede generar lenguajes regulares de forma similar a los autómatas finitos y expresiones regulares. Existen dos tipos de gramáticas regulares: las regulares derechas, cuyas reglas de producción van de símbolos no terminales a terminales o cadenas de símbolos, y las regulares izquierdas, cuyas reglas van de terminales o cadenas seguidos de símbolos no terminales. Es posible convertir una gramática regular izquierda a una derecha y viceversa usando algoritmos.

Cargado por

Germán Salas
Derechos de autor
© Attribution Non-Commercial (BY-NC)
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd
531 vistas2 páginas

Introducción a Gramáticas Regulares

Una gramática regular es una gramática formal que puede generar lenguajes regulares de forma similar a los autómatas finitos y expresiones regulares. Existen dos tipos de gramáticas regulares: las regulares derechas, cuyas reglas de producción van de símbolos no terminales a terminales o cadenas de símbolos, y las regulares izquierdas, cuyas reglas van de terminales o cadenas seguidos de símbolos no terminales. Es posible convertir una gramática regular izquierda a una derecha y viceversa usando algoritmos.

Cargado por

Germán Salas
Derechos de autor
© Attribution Non-Commercial (BY-NC)
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PDF, TXT o lee en línea desde Scribd

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. A → a, donde A es un símbolo no-terminal en N y a uno terminal en Σ


2. A → aB, 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. A → a, donde A es un símbolo no-terminal en N y a uno terminal en Σ


2. A → Ba, 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 (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.

[Link]

También podría gustarte