Automatas

Gram´ticas Formales
a
Jerarqu´ de Chomsky
ıa
Gram´ticas Libres de Contexto
a

Gram´ticas Libres de Contexto
a
Material de Apoyo

Andr´s Ram´ 1
e
ırez
1 Magister en Ingenier´ de Sistemas
ıa
Universidad Nacional de Colombia, 2010

Fundaci´n de Educaci´n Superior San Jos´, 2013
o
o
e

Andr´s Ram´
e
ırez

Lenguajes Formales

Gram´ticas Formales
a
Jerarqu´ de Chomskyıa
Gram´ticas Libres de Contexto
a

Outline
1

Gram´ticas Formales
a
Definiciones
Ejemplos

2

Jerarqu´ de Chomsky
ıa
Definici´n
o
Estructura de la Jerarqu´
ıa

3

Gram´ticas Libres de Contexto
a
Definici´n
o
Ejemplos
´
Arboles de Derivaci´n o An´lisis de Ambig¨edad
o
a
u

Andr´s Ram´
e
ırez

Lenguajes Formales

Gram´ticas Formales
a
Jerarqu´ de Chomsky
ıaGram´ticas Libres de Contexto
a

Definiciones
Ejemplos

Outline
1

Gram´ticas Formales
a
Definiciones
Ejemplos

2

Jerarqu´ de Chomsky
ıa
Definici´n
o
Estructura de la Jerarqu´
ıa

3

Gram´ticas Libres de Contexto
a
Definici´n
o
Ejemplos
´
Arboles de Derivaci´n o An´lisis de Ambig¨edad
o
a
u

Andr´s Ram´
e
ırez

Lenguajes Formales

Gram´ticas Formales
aJerarqu´ de Chomsky
ıa
Gram´ticas Libres de Contexto
a

Definiciones
Ejemplos

Lenguaje Formal

Un Lenguaje Formal est´ definido por conjuntos de cadenas
a
constituidas por s´
ımbolos pertenecientes a un alfabeto Σ donde la
generaci´n de tales cadenas puede estar determinada por un
o
conjunto de reglas espec´
ıficas y bien definidas.

Andr´s Ram´
e
ırez

Lenguajes FormalesGram´ticas Formales
a
Jerarqu´ de Chomsky
ıa
Gram´ticas Libres de Contexto
a

Definiciones
Ejemplos

Gram´tica Formal
a

En la Teor´ de Lenguajes Formales, una Gram´tica (Gram´tica
ıa
a
a
Formal o Regular) es un conjunto de Reglas de Producci´n que
o
permiten generar cadenas en un lenguaje formal.
Dichas reglas describen c´mo construir cadenas v´lidas sobre un
o
a
lenguaje dado(seg´n el alfabeto Σ) considerando la sintaxis del
u
lenguaje.

Andr´s Ram´
e
ırez

Lenguajes Formales

Gram´ticas Formales
a
Jerarqu´ de Chomsky
ıa
Gram´ticas Libres de Contexto
a

Definiciones
Ejemplos

Reglas de Producci´n
o

Una Regla de Producci´n es una regla de re-escritura que
o
especifica una sustituci´n de s´
o
ımbolos (en un lenguaje, en un
alfabeto) que se puedeejecutar de forma recursiva y cuyo objetivo
principal es generar una nueva secuencia de s´
ımbolos. T´
ıpicamente,
hablando de Gram´ticas, dichas reglas de producci´n son finitas.
a
o

Andr´s Ram´
e
ırez

Lenguajes Formales

Gram´ticas Formales
a
Jerarqu´ de Chomsky
ıa
Gram´ticas Libres de Contexto
a

Definiciones
Ejemplos

Definici´n Formal
o
Una Gram´tica Regular G esuna 4-tupla G = (Σ, N, S, P) donde:
a
Σ es el alfabeto.
N es una colecci´n de s´
o
ımbolos No Terminales.
S es un s´
ımbolo No terminal llamado S´
ımbolo Inicial.
P es una colecci´n de reglas de sustituci´n/producci´n
o
o
o
llamadas producciones. Dichas producciones son de la forma
A → w donde:
A∈N
w∈(Σ∪N)
w contiene un terminal como m´ximo
a
Si w contiene un terminal, entonces esel s´
ımbolo que est´ en
a
el extremo derecho de w.

Andr´s Ram´
e
ırez

Lenguajes Formales

Gram´ticas Formales
a
Jerarqu´ de Chomsky
ıa
Gram´ticas Libres de Contexto
a

Definiciones
Ejemplos

Outline
1

Gram´ticas Formales
a
Definiciones
Ejemplos

2

Jerarqu´ de Chomsky
ıa
Definici´n
o
Estructura de la Jerarqu´
ıa

3

Gram´ticas Libres de Contexto
aDefinici´n
o
Ejemplos
´
Arboles de Derivaci´n o An´lisis de Ambig¨edad
o
a
u

Andr´s Ram´
e
ırez

Lenguajes Formales

Gram´ticas Formales
a
Jerarqu´ de Chomsky
ıa
Gram´ticas Libres de Contexto
a

Definiciones
Ejemplos

Ejemplo 1

Figure : A=a(a* U b*)b

Andr´s Ram´
e
ırez

Lenguajes Formales

Gram´ticas Formales
a
Jerarqu´ de Chomsky
ıa
Gram´ticas Libres de...