xya tena2

Computabilidad y Algoritmia

Tema 2: Lenguajes y gram´ticas
a
independientes del contexto
Gara Miranda Valladares
Curso 2013-2014

Introducci´n
o
Gram´ticas regulares
a
Gram´ticas independientes del contexto
a

Indice

1

Introducci´n
o

2

Gram´ticas regulares
a

3

Gram´ticas independientes del contexto
a
Definiciones b´sicas y notaci´n
a
o
Simplificaci´n
oPropiedades

Gara Miranda Valladares

Tema 2: Lenguajes y gram´ticas independientes del contexto
a

Introducci´n
o
Gram´ticas regulares
a
Gram´ticas independientes del contexto
a

Indice

1

Introducci´n
o

2

Gram´ticas regulares
a

3

Gram´ticas independientes del contexto
a
Definiciones b´sicas y notaci´n
a
o
Simplificaci´n
o
Propiedades

Gara MirandaValladares

Tema 2: Lenguajes y gram´ticas independientes del contexto
a

Introducci´n
o
Gram´ticas regulares
a
Gram´ticas independientes del contexto
a

Introducci´n
o
Las expresiones regulares y los aut´matas finitos
o
Nos proporcionan dos medios para especificar o definir lenguajes.
Las expresiones regulares nos proporcionan una plantilla o patr´n
o
para las cadenas del lenguaje.
Unaut´mata finito especifica un lenguaje como el conjunto de todas
o
las cadenas que lo hacen pasar del estado inicial a uno de sus
estados de aceptaci´n:
o
Interpretar un aut´mata como un generador de cadenas del lenguaje.
o

Ejemplo: a(a∗ |b∗ )b

Gara Miranda Valladares

Tema 2: Lenguajes y gram´ticas independientes del contexto
a

Introducci´n
o
Gram´ticas regulares
a
Gram´ticasindependientes del contexto
a

Introducci´n
o
Ejemplo: a(a∗ |b∗ )b
Cadenas formadas por una “a” seguidas de una parte final: S → aE
Para la parte final tenemos dos opciones:
Cadenas de “aes” seguidas de una “b”: E → A, A → aA, A → b
Cadenas de “bes”: E → B, B → bB, B → b

Reglas de sustituci´n
o
S → aE
E→A
E→B
A→b
A → aA
B→b
B → bB
Gara Miranda Valladares

Tema 2: Lenguajes ygram´ticas independientes del contexto
a

Introducci´n
o
Gram´ticas regulares
a
Gram´ticas independientes del contexto
a

Introducci´n
o
Reglas de sustituci´n para la generaci´n de cadenas
o
o
S → aE
E→A
E→B
A→b
A → aA
B→b
B → bB

Abreviando...
S → aE
E → A|B
A → aA|b
B → bB|b
Gara Miranda Valladares

Tema 2: Lenguajes y gram´ticas independientes del contexto
aIntroducci´n
o
Gram´ticas regulares
a
Gram´ticas independientes del contexto
a

Introducci´n
o
Reglas de sustituci´n para la generaci´n de cadenas
o
o
S → aE
E → A|B
A → aA|b
B → bB|b

Elementos
S´
ımbolos terminales: s´
ımbolos del alfabeto = {a, b}
S´
ımbolos no terminales: colecci´n de nuevos s´
o
ımbolos para representar a las
porciones de cadenas que no han sidogeneradas = {S, E, A, B}
Reglas de producci´n:
o
< No terminal > → < Terminales y no terminales >
Lado izquierdo y lado derecho de las reglas de producci´n.
o
El s´
ımbolo que se encuentra a la izquierda de la flecha se puede sustituir por la
cadena de la derecha.
Gara Miranda Valladares

Tema 2: Lenguajes y gram´ticas independientes del contexto
a

Introducci´n
o
Gram´ticas regulares
aGram´ticas independientes del contexto
a

Introducci´n
o
Reglas de sustituci´n para la generaci´n de cadenas
o
o
S → aE
E → A|B
A → aA|b
B → bB|b

Ejemplo para generar la cadena aaab:
Comenzar con el s´
ımbolo de arranque S.
Coger el s´
ımbolo no terminal de la cadena y reemplazarlo por el lado
derecho de alguna regla que tenga ese s´
ımbolo en la parte izquierda.
Repetir elpaso anterior hasta que todos los s´
ımbolos de la cadena
sean s´
ımbolos terminales.
S ⇒ aE ⇒ aA ⇒ aaA ⇒ aaaA ⇒ aaab
Gara Miranda Valladares

Tema 2: Lenguajes y gram´ticas independientes del contexto
a

Introducci´n
o
Gram´ticas regulares
a
Gram´ticas independientes del contexto
a

Indice

1

Introducci´n
o

2

Gram´ticas regulares
a

3

Gram´ticas independientes...