Facultad de Ingeniería

Universidad Nacional Autónoma de México

Lenguajes Formales y Autómatas

Luis M. Estrada
luis.estrada@ingeniería.unam.edu
 Agenda
1

▪ Gramáticas Formales

Luis M. Estrada |
 Expresiones Regulares
3

Lenguaje Modelo descriptivo

Regulares Expresiones regulares
Libres de contexto
Sensibles al contexto
▪ ER: Modelo descriptivo
Recursivos

Luis M. Estrada |
 Gramáticas Formales
5

▪ Modelo generativo: Reglas para construir

cadenas bien formadas de un lenguaje

▪ La gramática es la que da estructura al lenguaje

(sintaxis)

Luis M. Estrada |
 Gramática
16

El estudio formal de las gramáticas lo inició Noam Chomsky en los 50’s

Al tratar de modelar la forma en que los humanos generamos y usamos el

lenguaje natural.
Luis M. Estrada |
 Gramáticas Formales
5

▪ Conjunto de reglas de sustitución (reescritura) de símbolo

Estos_símbolos → Por_estos
Cabeza se sustituyen Cuerpo

▪ Una o varias acciones de sustitución pueden generar

cadenas del lenguaje modelado por la gramática

Luis M. Estrada |
 Gramáticas Formales
5

▪ Conjunto de reglas de sustitución (reescritura) de símbolo

Estos_símbolos → Por_estos
Cabeza se sustituyen Cuerpo

Ejemplo: abXbcY → abcbca

▪ Una o varias acciones de sustitución pueden generar

cadenas del lenguaje modelado por la gramática

Luis M. Estrada |
 Gramáticas Formales
5

▪ Los símbolos involucrados en las reglas de la

gramática pueden ser de dos tipos:

▪ Terminales: Símbolos del alfabeto con los que se

construyen las cadenas

▪ Variables: símbolos especiales que no son parte del

alfabeto para construir cadenas

Luis M. Estrada |
 Gramáticas formales
10

Formalmente una gramática es una cuádrupla

(Σ, V, R, S) donde:
▪ Σ es el alfabeto del lenguaje (símbolos terminales)

Luis M. Estrada |
 Gramáticas formales
10

Formalmente una gramática es una cuádrupla

(Σ, V, R, S) donde:
▪ Σ es el alfabeto del lenguaje (símbolos terminales)

▪ V es un conjunto de símbolos llamados variables

Luis M. Estrada |
 Gramáticas formales
10

Formalmente una gramática es una cuádrupla

(Σ, V, R, S) donde:
▪ Σ es el alfabeto del lenguaje (símbolos terminales)

▪ V es un conjunto de símbolos llamados variables

▪ R es un conjunto de reglas de sustitución
de símbolos (producciones)

Luis M. Estrada |
 Gramáticas formales
10

Formalmente una gramática es una cuádrupla

(Σ, V, R, S) donde:
▪ Σ es el alfabeto del lenguaje (símbolos terminales)

▪ V es un conjunto de símbolos llamados variables

▪ R es un conjunto de reglas de sustitución de
símbolos (producciones)
▪ S es una variable designada como símbolo
inicial

Luis M. Estrada |
 Ejemplo 1:
25

Σ= {a,b,c}
V= {S,X,Y}
Variable inicial: S
Reglas:
S → aX
X→ b
X → bY
Y→c

Luis M. Estrada |
 Ejemplo 1:
25

Σ= {a,b,c}
V= {S,X,Y}
Variable inicial: S
Reglas:
S → aX Cuando dos o más regl as
X→ b tienen la misma cabeza se
suele poner solo una vez la
X → bY cabeza y juntar los cuerpos
Y→c de las regl as con un |

Luis M. Estrada |
 Ejemplo 1:
25

Σ= {a,b,c}
V= {S,X,Y}
Variable inicial: S
Reglas:
S → aX Cuando dos o más regl as
X → b | bY tienen la misma cabeza se
suele poner solo una vez la
X→ bY cabeza y juntar los cuerpos
Y→c de las regl as con un |

Se lee: “o por”

Luis M. Estrada |
 Ejemplo 1:
25

En pro de la simplicidad frecuentemente solo

haremos explícito el conjunto de reglas, es así
que sin ambiguedad G1 la expresamos
simplemente como:

S→aX
X→bY | b
Y→c

Luis M. Estrada |
 Forma sentencial
25

Una cadena en forma sentencial es una cadena

con variables y símbolos terminales.

Por ejemplo, si A y B son variables, y c y d

símbolos terminales, entonces las siguientes
cadenas están en forma sentencial:
• cAdBd
• BAcd
• Accd
• cB

Luis M. Estrada |
 Derivación
25

Es el proceso de generar cadenas válidas de un

lenguaje siguiendo las reglas de la gramática del
lenguaje.

El proceso comienza con la variable inicial de la

gramática y la posterior aplicación de una sucesión
de reglas de sustitución hasta obtener una cadena
sin variables, o bien hasta que no sea posible aplicar
más reglas.

Luis M. Estrada |
 Ejemplo 1: Tabla de derivación
25

¿podremos generar la cadena abc?

S → aX
X → b | bY
Y→c Regla aplicada Cadena

Luis M. Estrada |
 Ejemplo 1: Tabla de derivación
25

¿podremos generar la cadena abc?

S → aX
X → b | bY
Y→c Regla aplicada Cadena

S
S → aX aX

Luis M. Estrada |
 Ejemplo 1: Tabla de derivación
25

¿podremos generar la cadena abc?

S → aX
X → b | bY
Y→c Regla aplicada Cadena

S
S → aX aX
X → bY abY

Luis M. Estrada |
 Ejemplo 1: Tabla de derivación
25

¿podremos generar la cadena abc?

S → aX
X → b | bY
Y→c Regla aplicada Cadena

S
S → aX aX
X → bY abY

Y→c abc

Luis M. Estrada |
 Ejemplo 1: Tabla de derivación
25

¿podremos generar también la cadena ab?

S → aX
X → b | bY
Y→c Regla aplicada Cadena

S
S → aX aX
X → bY abY

Y→c abc

Luis M. Estrada |
 Ejemplo 1: Tabla de derivación
25

¿podremos generar también la cadena ab?

S → aX
X → b | bY
Y→c Regla aplicada Cadena

S
S → aX aX
X → bY abY

Y→c abc

El lenguaje generado por esta gramática es {ab,abc}

Luis M. Estrada |
 Ejemplo 1: Tabla de derivación
25

Podemos simplificar la gramática…

S → ab | abc

Regla aplicada Cadena

S
S → ab ab

El lenguaje generado por esta gramática es {ab,abc}

Luis M. Estrada |
 Ejemplo 1: Tabla de derivación
25

Si no nos interesa hacer explícita la regla aplicada, sino simplemente la

secuencia de formas sentenciales que llevan desde la variable inicial a la
cadena de terminales, utilizamos el símbolo ⇒.

Regla aplicada Cadena

S
S → aX aX
X → bY abY

Y→c abc

La misma derivación de la tabla anterior la podemos describir como:

S ⇒ aX ⇒ abY ⇒ abc

Si solo nos interesa el fin del proceso escribimos: S ⇒* abc

Luis M. Estrada |
 Lenguaje generado por una gramática
10

En cada forma sentencial del proceso derivación podríamos tener más de

una variable para sustituir. Considere por ejemplo la gramática:

S → aSaX | aaX
X→b

En el segundo paso de la derivación S ⇒ aSaX tenemos dos variables,

en el siguiente paso surge la pregunta ¿cuál de las dos variables sustituir?

Luis M. Estrada |
 Lenguaje generado por una gramática
10

Cuando en cada paso de la derivación se sustituye la variable más a la

izquierda se denomina derivación a la izquierda, por el contrario cuando en
cada paso se sustituye la variable más a la derecha se denomina derivación
a la derecha.

Por lo tanto con derivaciones a la izquierda tendríamos

S ⇒ aSaX ⇒ aaaXaX ⇒ aaabaX ⇒ aaabab

Mientras que con derivaciones a la derecha tendríamos:

S ⇒ aSaX ⇒ aSab ⇒ aaaXab ⇒ aaabab

Luis M. Estrada |
 Derivación de cadenas
5

Sea G una gramática para un lenguaje L, y sea S

la variable inicial de G.

▪ Decimos que una cadena w de L es derivable

de G, y escribimos S ⇒* w, si partiendo con la
variables S y aplicando una secuencia de
reglas de sustitución podemos obtener la
cadena w.

Luis M. Estrada |
 Lenguaje generado por una gramática
10

Diremos que una gramática G es una gramática

para L si a partir de G se pueden derivar todas las
cadenas en L y solo cadenas de L.

L(G) = {w ∈ Σ* | S ⇒* w}

Luis M. Estrada |
 Lenguajes y sus gramáticas
3

Lenguaje Modelo generativo

Tipo 3 G. Regulares
Tipo 2 G. Libres de contexto
Tipo 1 G. Sensibles al contexto
▪ ER: Modelo descriptivo
Tipo 0 G. Sin restricciones

Luis M. Estrada |
 30

¡A construir gramáticas!

Luis M. Estrada |
 Ejemplos 2:
30

Gramática para el lenguaje {λ}

Luis M. Estrada |
 Ejemplos 2:
30

Gramática para el lenguaje {λ}

Derivación de λ
S→λ
Regla aplicada Cadena

S
S→λ λ

Luis M. Estrada |
 Ejemplos 2:
30

Gramática para el lenguaje {a}

Luis M. Estrada |
 Ejemplos 2:
30

Gramática para el lenguaje {a}

Derivación de a
S→a
Regla aplicada Cadena

S
S→a a

Luis M. Estrada |
 Ejemplo 2:
30

Gramática para el lenguaje a∗

Luis M. Estrada |
 Ejemplo 2:
30

Gramática para el lenguaje a∗

S → λ| aS Derivación de aaa

Regla aplicada Cadena

S
S → aS aS
S → aS aaS

S → aS aaaS

S→ λ aaa

Luis M. Estrada |
 Ejemplo 3:
37

Gramática para el lenguaje {a, b}∗

Luis M. Estrada |
 Ejemplo 3:
37

Gramática para el lenguaje {a, b}∗

S → λ |aS | bS Derivación de babb

Regla aplicada Cadena

S
S → bS bS
S → aS baS

S → bS babS

S → bS babbS

S→ λ babb
Luis M. Estrada |
 Ejemplo 3':
37

Gramática para el lenguaje a*b∗

Luis M. Estrada |
 Ejemplo 3':
37

Gramática para el lenguaje a*b∗

S → λ |aS | aB Derivación de aabb

Regla aplicada Cadena

B → b | bB
S

Luis M. Estrada |
 Ejemplo 4:
44

Gramática para el lenguaje (ab) ∗

Luis M. Estrada |
 Ejemplo 4:
44

Gramática para el lenguaje (ab) ∗

S → λ | abS
Derivación de abab

Regla aplicada Cadena

S
S → abS abS

Luis M. Estrada |
 Ejemplo 6:
55

Dar una gramática que genere el lenguaje de cadenas

con el alfabeto {a, b} que contengan la subcadena bb.

Luis M. Estrada |
 Ejemplo 6:
55

Dar una gramática que genere el lenguaje de cadenas

con el alfabeto {a, b} que contengan la subcadena bb.

S → bbB | aS | baS
B → λ | aB | bB

Luis M. Estrada |
 Ejemplo 6:
55

Dar una gramática que genere el lenguaje de cadenas

con el alfabeto {a, b} que contengan la subcadena bb.

No se debe poder derivar aab

S → bbB | aS | baS Regla aplicada Cadena
B → λ | aB | bB S
S → aS aS

Luis M. Estrada |
 Ejemplo 6:
55

Dar una gramática que genere el lenguaje de cadenas

con el alfabeto {a, b} que contengan la subcadena bb.

No se debe poder derivar aab

S → bbB | aS | baS Regla aplicada Cadena
B → λ | aB | bB S
S → aS aS
S → aS aaS

Luis M. Estrada |
 Ejemplo 6:
55

Dar una gramática que genere el lenguaje de cadenas

con el alfabeto {a, b} que contengan la subcadena bb.

No se debe poder derivar aab

S → bbB | aS | baS Regla aplicada Cadena
B → λ | aB | bB S
S → aS aS
S → aS aaS
no ha y r eg l a qu e
pe r mi t a ge ne r ar un a
b y de s ha c er no s de
l a v ar i abl e S

Luis M. Estrada |
 Ejemplo 6:
55

Dar una gramática que genere el lenguaje de cadenas

con el alfabeto {a, b} que contengan la subcadena bb.
Derivación de ababbb
S → bbB | aS | baS Regla aplicada Cadena
B → λ | aB | bB S
S → aS aS

Luis M. Estrada |
 Ejemplo 6:
55

Dar una gramática que genere el lenguaje de cadenas

con el alfabeto {a, b} que contengan la subcadena bb.
Derivación de ababbb
S → bbB | aS | baS Regla aplicada Cadena
B → λ | aB | bB S
S → aS aS
S → b aS abaS

Luis M. Estrada |
 Ejemplo 6:
55

Dar una gramática que genere el lenguaje de cadenas

con el alfabeto {a, b} que contengan la subcadena bb.
Derivación de ababbb
S → bbB | aS | baS Regla aplicada Cadena
B → λ | aB | bB S
S → aS aS
S → b aS abaS

S → b bB ababbB

Luis M. Estrada |
 Ejemplo 6:
55

Dar una gramática que genere el lenguaje de cadenas

con el alfabeto {a, b} que contengan la subcadena bb.
Derivación de ababbb
S → bbB | aS | baS Regla aplicada Cadena
B → λ | aB | bB S
S → aS aS
S → b aS abaS

S → b bB ababbB

B → bB ababbbB

Luis M. Estrada |
 Ejemplo 6:
55

Dar una gramática que genere el lenguaje de cadenas

con el alfabeto {a, b} que contengan la subcadena bb.
Derivación de ababbb
S → bbB | aS | baS Regla aplicada Cadena
B → λ | aB | bB S
S → aS aS
S → b aS abaS

S → b bB ababbB

B → bB ababbbB

B→ λ ababbb

Luis M. Estrada |
 Ejemplo 7:
58

Diseñar una gramática para ab∗c

Solución:

Luis M. Estrada |
 Ejemplo 7:
58

Diseñar una gramática para ab∗c

Solución:
S → aBc
B → λ | bB

Luis M. Estrada |
 Ejemplo 7:
58

Diseñar una gramática para b(aaa)*b

Solución:

Luis M. Estrada |
 Ejemplo 7:
58

Diseñar una gramática para b(aaa)*b

Solución:
S → bAb
A → λ| aaaA

Luis M. Estrada |
 Ejemplo 8:
58

Diseñar una gramática para el lenguaje {anbn| n≥0}

Derivación de a3b3
Solución?:

Luis M. Estrada |
 Ejemplo 8:
58

Diseñar una gramática para el lenguaje {anbn| n≥0}

Derivación de a3b3
Solución?: Regla aplicada Cadena

S → aS | bS | λ S
S → aS aS
S → aS aaS

S → aS aaaS

S → bS aaabS

S → bS aaabbS

S → bS aaabbbS

S→ λ aaabbb
Luis M. Estrada |
 Ejemplo 8:
58

Diseñar una gramática para el lenguaje {anbn| n≥0}

Solución:
Derivación de a3b3
S → aSb | λ
Regla aplicada Cadena

S
S → aSb aSb

Luis M. Estrada |
 Ejemplo 9:
58

Diseñar una gramática para el lenguaje de

palíndromos con {a,b}

¿Qué es un palíndromo?

anita lava la tina

reconocer

Luis M. Estrada |
 Ejemplo 9:
58

Diseñar una gramática para el lenguaje de

palíndromos con {a,b}

Ejemplos de palíndromos:
abaaba

abababa

No es palíndromo:
ababba

Luis M. Estrada |
 Ejemplo 9:
58

Diseñar una gramática para el lenguaje de

palíndromos con {a,b}

Solución:

Luis M. Estrada |
 Ejemplo 9:
58

Diseñar una gramática para el lenguaje de

palíndromos con {a,b}

Solución:
S → aSa | bSb | a | b

Luis M. Estrada |
 Ejemplo 10:
26

Diseñar una gramática que genere cadenas de

paréntesis anidados equilibrados, es decir
cadenas como: (), ((())), ()()(), ()(())

Luis M. Estrada |
 Ejemplo 10:
26

Diseñar una gramática que genere cadenas de

paréntesis anidados equilibrados, es decir
cadenas como: (), ((())), ()()(), ()(()), (())((()))

Solución?:

Luis M. Estrada |
 Ejemplo 10:
26

Diseñar una gramática que genere cadenas de

paréntesis anidados equilibrados, es decir
cadenas como: (), ((())), ()()(), ()(()), (())((()))

Solución:

S → (S)S | λ

Luis M. Estrada |
 Ejemplo 11:
28

Diseñar una gramática para el lenguaje

{a n b m c m d n : n, m ≥ 1}

Luis M. Estrada |
 Ejemplo 11:
28

Diseñar una gramática para el lenguaje

{a n b m c m d n : n, m ≥ 1}

Solución:

S → aSd | aXd

X → bXc | bc

Luis M. Estrada |
 Ejemplo 12:
30

Encontrar una gramática para el lenguaje

{a n b m c n + m : n ≥ 0, m ≥ 1}

Luis M. Estrada |
 Ejemplo 12:
30

Encontrar una gramática para el lenguaje

{a n b m c n + m : n ≥ 0, m ≥ 1}

Solución:

S → aSc | B

B → bBc | bc

Luis M. Estrada |
 Ejemplo 12:
30

Encontrar una gramática para el lenguaje

{a n b n c n : n ≥ 1}
Derivación de aabbcc
¿Solución?: Regla aplicada Cadena

Luis M. Estrada |
 Ejemplo 12:
30

Encontrar una gramática para el lenguaje

{a n b n c n : n ≥ 1}
Derivación de a3b3c3
¿Solución?: ✘ Regla aplicada Cadena

S → aSbc | abc

Luis M. Estrada |
 Ejemplo 12:
30

Encontrar una gramática para el lenguaje

{a n b n c n : n ≥ 1} Derivación de a3b3c3
Regla aplicada Cadena
¿Solución?:
S → aSBc | abc
cB → Bc
bB → bb

Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

{ww : w ∈ {a,b}*}

Ejemplos de cadenas:

abababab
w w

Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

{ww : w ∈ {a,b}*}

Ejemplos de cadenas:

abababab
w w
ababbaba
m1 m2

Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

{ww : w ∈ {a,b}*}

Ejemplos de cadenas:

abababab
w w
abababab
m 1 (m 2 ) R

Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: S
S → PF
P → aPa| bPb| λ

Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: S
S → PF S → PF PF
P → aPa| bPb| λ

Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: S
S → PF S → PF PF
P → aPa| bPb| λ P → aPa aPaF

Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: S
S → PF S → PF PF
P → aPa| bPb| λ P → aPa aPaF

P → bPb abPbaF

Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: S
S → PF S → PF PF
P → aPa| bPb| λ P → aPa aPaF

P → bPb abPbaF

P → bPb abbPbbaF

Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: S
S → PF S → PF PF
P → aPa| bPb| λ P → aPa aPaF

P → bPb abPbaF

P → bPb abbPbbaF

P→ λ abbbbaF

Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: S
S → PF S → PF PF
P → aPa| bPb| C P → aPa aPaF

P → bPb abPbaF

P → bPb abbPbbaF

P→ C abbCbbaF

Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: abbCbbaF
S → PF
P → aPa| bPb| C
C →CI
Iab → bIa
Iba → aIb
Iaa → aIa
Ibb → bIb
Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: abbCbbaF
S → PF C → CI abbCIbbaF
P → aPa| bPb| C
C →CI
Iab → bIa
Iba → aIb
Iaa → aIa
Ibb → bIb
Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: abbCbbaF
S → PF C → CI abbCIbbaF
P → aPa| bPb| C Ibb → bIb abbCbIbaF
C →CI
Iab → bIa
Iba → aIb
Iaa → aIa
Ibb → bIb
Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: abbCbbaF
S → PF C → CI abbCIbbaF
P → aPa| bPb| C Ibb → bIb abbCbIbaF
C →CI Iba → aIb abbCbaIbF
Iab → bIa
Iba → aIb
Iaa → aIa
Ibb → bIb
Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: abbCbbaF
S → PF C → CI abbCIbbaF
P → aPa| bPb| C Ibb → bIb abbCbIbaF
C →C I
Iab → bIa Iba → aIb abbCbaIbF
Iba → aIb
Iaa → aIa
Ibb → bIb
IbF → Fb
IaF → Fa
Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: abbCbbaF
S → PF C → CI abbCIbbaF
P → aPa| bPb| C Ibb → bIb abbCbIbaF
C →C I
Iab → bIa Iba → aIb abbCbaIbF
Iba → aIb IbF → Fb abbCbaFb
Iaa → aIa
Ibb → bIb
IbF → Fb
IaF → Fa
Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: abbCbbaF
S → PF C → CI abbCIbbaF
P → aPa| bPb| C Ibb → bIb abbCbIbaF
C →C I
Iab → bIa Iba → aIb abbCbaIbF
Iba → aIb IbF → Fb abbCbaFb
Iaa → aIa
C → CI abbCIbaFb
Ibb → bIb
IbF → Fb
IaF → Fa
Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: abbCbbaF
S → PF C → CI abbCIbbaF
P → aPa| bPb| C Ibb → bIb abbCbIbaF
C →C I
Iab → bIa Iba → aIb abbCbaIbF
Iba → aIb IbF → Fb abbCbaFb
Iaa → aIa
C → CI abbCIbaFb
Ibb → bIb
IbF → Fb Iba → aIb abbCaIbFb
IaF → Fa
Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: abbCbbaF
S → PF C → CI abbCIbbaF
P → aPa| bPb| C Ibb → bIb abbCbIbaF
C →C I
Iab → bIa Iba → aIb abbCbaIbF
Iba → aIb IbF → Fb abbCbaFb
Iaa → aIa
C → CI abbCIbaFb
Ibb → bIb
IbF → Fb Iba → aIb abbCaIbFb
IaF → Fa IbF → Fb abbCaFbb
Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: IbF → Fb abbCaFbb

S → PF
P → aPa| bPb| C
C →C I
Iab → bIa
Iba → aIb
Iaa → aIa
Ibb → bIb
IbF → Fb
IaF → Fa
Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: IbF → Fb abbCaFbb

S → PF C →CI abbCIaFbb
P → aPa| bPb| C
C →C I
Iab → bIa
Iba → aIb
Iaa → aIa
Ibb → bIb
IbF → Fb
IaF → Fa
Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: IbF → Fb abbCaFbb

S → PF C →CI abbCIaFbb
P → aPa| bPb| C IaF → Fa abbCFabb
C →C I
Iab → bIa
Iba → aIb
Iaa → aIa
Ibb → bIb
IbF → Fb
IaF → Fa
Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

Derivación de abbabb
{ww : w ∈ {a,b}*}
Regla aplicada Cadena

Solución: IbF → Fb abbCaFbb

S → PF C →CI abbCIaFbb
P → aPa| bPb| C IaF → Fa abbCFabb
C →C I
Iab → bIa CF → λ abbabb
Iba → aIb
Iaa → aIa
Ibb → bIb
IbF → Fb
IaF → Fa CF → λ
Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

{ww : w ∈ {a,b}*}

Otra solución con una gramática que no borre

símbolos

Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

{ww : w ∈ {a,b}*}

Solución:
S → aXa| bXb| λ
X → aXa| bXb | aa | bb

Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

{ww : w ∈ {a,b}*}

Solución:
S → aXFa| bXFb| λ
X → aXa| bXb | CaPa| CbPb

Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

{ww : w ∈ {a,b}*}

Solución:
S → aXFa| bXFb| λ
X → aXa| bXb | CaPa| CbPb
Pab → bPa
Pba → aPb
Paa → aPa
Pbb → bPb

Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

{ww : w ∈ {a,b}*}

Solución:
S → aXFa| bXFb| λ PaFa → Faa
X → aXa| bXb | CaPa| CbPb PaFb → Fba
Pab → bPa PbFa → Fab
Pba → aPb PbFb → Fbb
Paa → aPa
Pbb → bPb

Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

{ww : w ∈ {a,b}*}

Solución:
S → aXFa| bXFb| λ PaFa → Faa
X → aXa| bXb | CaPa| CbPb PaFb → Fba
Pab → bPa PbFa → Fab
Pba → aPb PbFb → Fbb
Paa → aPa Caa → CaPa
Pbb → bPb Cab → CaPb
Cba → CbPa
Cbb → CbPb

Luis M. Estrada |
 Ejemplo 13:
30

Encontrar una gramática para el lenguaje

{ww : w ∈ {a,b}*}

Solución:
S → aXFa| bXFb| λ PaFa → Faa CaFb → ab
X → aXa| bXb | CaPa| CbPb PaFb → Fba CaFa → aa
Pab → bPa PbFa → Fab CbFb → bb
Pba → aPb PbFb → Fbb CbFa → ba
Paa → aPa Caa → CaPa
Pbb → bPb Cab → CaPb
Cba → CbPa
Cbb → CbPb

Luis M. Estrada |
Regla aplicada Cadena

S
S →aXFa aXFa

X → bXb abXbFa Continuación de la derivación

X → aXa abaXabFa Regla aplicada Cadena

X → C bP b abaCb Pb abFa P aF a → F aa abaCbbPaFab

P ba → a P b abaCbaPbbFa PaFa → Faa abaCbbFaab

P bb → b P b abaCbabPbFa C bb → C b P b abaCbPbFaab

P bF a → F ab abaCbabFab P bF a → F a b abaCbFabab

C aa → C aP a abaCbPabFab CbFa → ba abababab

 Ejemplo 13:
30

Gramática para el lenguaje a2n (cadenas con una cantidad

de a’s potencia de dos) para cualquier n ≥ 0

Luis M. Estrada |
 Ejemplo 13:
30

Gramática para el lenguaje a2n (cadenas con una cantidad

de a’s potencia de dos) para cualquier n ≥ 0

a n=0
aa n=1
aaaa n=2
aaaaaaaa n=3
aaaaaaaaaaaaaaaa n=4

Luis M. Estrada |
 Ejemplo 13:
30

Gramática para el lenguaje a2n (cadenas con una cantidad

de a’s potencia de dos)

S → EaF
E → λ | EN
Na → aaN
NF → F
F→ λ

Luis M. Estrada |
 Ejemplo 13:
30

S → EaF Regla Cadena

E → λ | EN S
Na → aaN
S → EaF EaF
NF → F
F→ λ E → EN ENaF
E → EN ENNaF
S → EN ENNNaF

E→λ NNNaF
… …

Luis M. Estrada |
 Ejemplo 13:
30

S → EaF Regla Cadena

E → λ | EN NNNaF
E→λ
Na → aaN
Na → aaN NNaaNF
NF → F
F→ λ NF → F NNaaF
Na → aaN NaaNaF
Na → aaN NaaaaNF
NF → F NaaaaF

… …

Luis M. Estrada |
 Ejemplo 13:
30

S → EaF Regla Cadena

E → λ | EN NF → F NaaaaF
Na → aaN
Na → aaN aaNaaaF
NF → F
F→ λ Na → aaN aaaaNaaF
Na → aaN aaaaaaNaF
Na → aaN aaaaaaaaNF
NF → F aaaaaaaaF
F→ λ aaaaaaaa

Luis M. Estrada |
 Resumen
30

Tipo Sentido de la Mover símbolos Borrar símbolos

generación

Regulares →o← No No

L. Contexto → y/o ← No No

S. Contexto → y/o ← Sí No

Sin → y/o ← Sí Sí
restriccones

Luis M. Estrada |
 Lenguajes y sus gramáticas
42

Generados por gramáticas: Regulares

1. lineal por la derecha:

Tipo 0
• V→ β
• V → βW
Tipo 1
2. lineal por la izquierda:
Tipo 2
• V→ β
• V → Wβ

Tipo 3 Donde V y W son variables, y β ∈ Σ*

Luis M. Estrada |
 Lenguajes y sus gramáticas
42

Generados por gramáticas: Regulares

1. lineal por la derecha:

Tipo 0
• V→ β
• V → βW
Tipo 1
2. lineal por la izquierda:
Tipo 2
• V→ β
• V → Wβ

Tipo 3 Donde V y W son variables, y β ∈ Σ*

Lineales por la derecha:

Ej1:
S → aX
X → b | bY
Y→c
Luis M. Estrada |
 Lenguajes y sus gramáticas
42

Generados por gramáticas: Regulares

1. lineal por la derecha:

Tipo 0
• V→ β
• V → βW
Tipo 1
2. lineal por la izquierda:
Tipo 2
• V→ β
• V → Wβ

Tipo 3 Donde V y W son variables, y β ∈ Σ*

Lineales por la derecha:

Ej2:
S → bbB | aS |baS
B → λ | aB |bB

Luis M. Estrada |
 Lenguajes y sus gramáticas
42

Generados por gramáticas: Regulares

1. lineal por la derecha:

Tipo 0
• V→ β
• V → βW
Tipo 1
2. lineal por la izquierda:
Tipo 2
• V→ β
• V → Wβ

Tipo 3 Donde V y W son variables, y β ∈ Σ*

Lineales por la izquierda:

Ej3:
S → Sab |λ

Luis M. Estrada |
 Lenguajes y sus gramáticas
42

Generados por gramáticas: Libres de Contexto

Las reglas son de la forma:

Tipo 0
X →β

Tipo 1 Donde β es una cadena de

Tipo 2 terminalesy/o variables

o bien la cadena vacía.

Tipo 3

Ej1:
S → aSa | bSb | a | b
Luis M. Estrada |
 Lenguajes y sus gramáticas
42

Generados por gramáticas: Libres de Contexto

Las reglas son de la forma:

Tipo 0
X →β

Tipo 1 Donde β es una cadena de

Tipo 2 terminalesy/o variables

o bien la cadena vacía.

Tipo 3

Ej2:
S → (S)S | λ
Luis M. Estrada |
 Lenguajes y sus gramáticas
42

Generados por gramáticas: Sensibles al Contexto

La reglas son de la forma:

Tipo 0
α1Vα2 → β

Tipo 1 Donde α1, α2 y β son una

combinación de terminales
Tipo 2 y/o variables o λ

Y además |α1Vα2| ≤ |β|

Tipo 3

Luis M. Estrada |
 Lenguajes y sus gramáticas
42

Generados por gramáticas: Sensibles al Contexto

La reglas son de la forma:

Tipo 0
α1Vα2 → β

Tipo 1 Donde α1, α2 y β son una

combinación de terminales
Tipo 2 y/o variables o λ

Con la restricción |α1Vα2| ≤ |β|

Tipo 3
Ej1:
S → aSBc |abc
cB → B c
bB → bb

Luis M. Estrada |
 Lenguajes y sus gramáticas
42

Generados por gramáticas: Gramáticas sin restricciones

La reglas son de la forma:

α1Vα2 → β
Tipo 0

Donde α1, α2 y β son una

Tipo 1
combinación de terminales
y/o variables o λ
Tipo 2

Tipo 3

Luis M. Estrada |
 Lenguajes y sus gramáticas
42

Generados por gramáticas: Gramáticas sin restricciones

La reglas son de la forma:

α1Vα2 → β
Tipo 0

Donde α1, α2 y β son una

Tipo 1
combinación de terminales
y/o variables o λ Ej1:
Tipo 2 S → PF
P → aPa|
bPb|C
C →CI
Tipo 3 Iab → bIa
Iba → aIb
Iaa → aIa
Ibb → bIb
IbF → Fb
IaF → Fa
CF → λ
Luis M. Estrada |
 Árbol de derivación
28

El árbol de análisis sintáctico o

arbol de derivación, es una
representación de la estructura
sintáctica de una cadena de
acuerdo una gramática dada. S

X Y

a X Y c
b λ
c
 Ejemplo 10:
26

Solución:
S → (S)S | λ
Derivación de (())
Regla aplicada Cadena
S
S

Luis M. Estrada |
 Ejemplo 10:
26

Solución:
S → (S)S | λ
Derivación de (())
Regla aplicada Cadena
S
S

( S ) S S → (S)S (S)S

Luis M. Estrada |
 Ejemplo 10:
26

Solución:
S → (S)S | λ
Derivación de (())
Regla aplicada Cadena
S
S

( S ) S S → (S)S (S)S
S → (S)S ((S)S)S

( S ) S

Luis M. Estrada |
 Ejemplo 10:
26

Solución:
S → (S)S | λ
Derivación de (())
Regla aplicada Cadena
S
S

( S ) S S → (S)S (S)S
S → (S)S ((S)S)S

S→ λ (()S)S
( S ) S

Luis M. Estrada |
 Ejemplo 10:
26

Solución:
S → (S)S | λ
Derivación de (())
Regla aplicada Cadena
S
S

( S ) S S → (S)S (S)S
S → (S)S ((S)S)S

S→ λ (()S)S
( S ) S
S→ λ (())S

λ λ

Luis M. Estrada |
 Ejemplo 10:
26

Solución:
S → (S)S | λ
Derivación de (())
Regla aplicada Cadena
S
S

( S ) S S → (S)S (S)S
S → (S)S ((S)S)S

S→ λ
( S ) S λ (()S)S

S→ λ (())S

λ λ S→λ (())

Luis M. Estrada |
 Resumen
42

Gramática Reglas Ejemplo de lenguaje

Regulares (Tipo 3) X→β X→β (a|b)*

X → βY X→Yβ
con β ∈ Σ*

Libres de contexto (Tipo 2) X →β con β ∈ (VUΣ )* a n bn

Sensibles al contexto (Tipo 1) α 1 Xα 2 → β con α 1 , α 2 , β ∈ (VUΣ )* y |α1Xα2| ≤ |β| an bncn

Sin restricciones (Tipo 0) α 1 Xα 2 → β con α 1 , α 2 , β ∈ (VUΣ )* ww con w ∈ {a,b}*

Tipo 0

Tipo 1

Tipo 2

Tipo 3