Gramáticas Regulares

27 10 2010

Definicion de la Gramática: Sirven para describir como se genera las cadenas de lenguaje. Estan construidas atravez de cuádruplas.

Definicion Formal: Definida por  G=(N,T,P,S) donde:

N= Conjunto finito de simbolos no terminales.

TConjunto finito de simbolos terminales.

P= Conjunto finito de producciones.

S= simbolos distinguidos o axioma agresividad.

Caracteristicas:

Conjunto finito de simbolos no terminales(N)

  • Por lo general son representados por medio de las letras o palabras en mayúsculas.

Simbolo Inicial(S)

  • Simbolo no terminal que representa el inicio de la gramática.
  • Por lo general se utiliza la letra S.

Conjunto finito de simbolos terminales (T)

  • Por lo general son representados por medio de letras o palabras en minúsculas.

Conjunto finito de producciones (P)

  • Utiliza en el lado izquierdo un símbolo no terminal.
  • El lado derecho una secuencia de símbolos terminales y no terminales; también pueden ser una cadena vacía (ε).

Gramáticas Regulares

Definición:

  • Es una gramática formal que adquirio gran importacia para el desarrollo de lenguajes de programación.
  • Las gramáticas regulares sólo pueden generar a los lenguajes regulares de manera similar alos automatas finitos y las expresiones regulares.

Las gramáticas regulares de dividen dependiendo de la estructura de las producciones, esto depende de la dirección hacia la que se expanden:

  1. Gramática Regular Derecha: Los simbolos no terminales se ubican al lado derecho de la producción(P) son de la siguiente forma:
  • Aa, A es un símbolo no-terminal en N y a uno terminal en T(terminal).
  • AaB, donde A y B pertenecen a N(no terminal) y a pertenece a T(terminal).
  • A → ε, donde A pertenece a (no terminal).
  1. Gramática Regular Izquierdo:Los símbolos no terminales se ubican al lado izquierdo de la producción ,sus reglas son las siguientes:
  • Aa, donde A es un símbolo no-terminal en N y a uno terminal en T (terminal).
  • ABa, donde A y B pertenecen a N (no terminal) y a pertenece a T (terminal).
  • A → ε, donde A pertenece a N (no terminal).

En ambos casos se incluye A → ε, si el lenguaje que se quiere generar es  coniene una cadena vacia.

Nota:

  • Donde A Y B son NO TERMINALES
  • Donde a es TERMINAL.

Aplicación de las reclas de Gramática Regular Izquierda y Derecha.

Gramática Regular a la derecha

G1=({H,I}, {a}, P1,S1)

S1→ε

S1→aH

H→aI

H→a

I→aH

Gramática Regular a la Izqierda

G2=({C,D}, {a}, P2,S2)

S2→ε

S2→Ca

C→Da

C→a

D→Ca

Ejemplo:

Ejercicio Nº1

 

G = (N, T, P, S)

  • N = {a, b, c, S, A, B}

 

  • T = {a, b, c}

 

  • PSAccA ABA |ε Ba | b | c
  • w1 = abcc L(G)   y w2 = acb L(G)

 

Ejercicio Nº2


Gramática G con V = {a, b, S, A}, T= {a, b}, variables = {S, A}, el símbolo inicial es S y las reglas de producción son:

S aS | aA A bA | b


G y M son equivalentes, ambos reconocen a+b+.

Bibliografia:

G = (V, S, R, S)
V = {a, b, c, S, A, B}
S = {a, b, c}
R: S ® AccA A ® BA | l B ® a | b | c

w1 = abcc Î L(G)   y w2 = acb Ï L(G)

Cadena Regla Derivación

S S ® AccA S Þ AccA

AccA A ® BA Þ BAccA

BAccA B ® a Þ aAccA

aAccA A ® BA Þ aBAccA

aBAccA B ® b Þ abAccA

abAccA A ® l Þ abccA

abccA A ® l Þ abcc

Licencia de Creative Commons
Este obra está bajo una licencia de Creative Commons Reconocimiento-CompartirIgual 3.0 Unported.


Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: