Matediscretas
Páginas: 5 (1204 palabras)
Publicado: 12 de mayo de 2011
Trabajo VIII
Semestre A2005
Problemas
Problemas de Lenguajes y Autómatas
1. Para los lenguajes dados sobre Σ = {a, b} construir una expresión regular de él y un Autómata Finito que lo acepte: a) L = {w|w tiene un numero par de a′ s} b) L = {w|w tiene un numero impar de a′ s} c) L = {w|w tiene un numero múltiplo de 3 de a′ s} d ) L = {w| toda a en w está entre dos b′ s} e) L = {w| nohay dos a′ s consecutivas en w} f ) L = {w| w no contiene la subpalabra aa ni bb} 2. Solución a) Una expresión regular que represente el lenguaje L es b∗ (ab∗ ab∗ )∗ . El diagrama de transición de un Autómata Finito es: b a b
a b) Una expresión regular para este lenguaje es: b∗ ab∗ (ab∗ ab∗ )∗ . El diagrama de transición de un Autómata Finito es: b a b
a c) Una expresión regular para estelenguaje es: b∗ (ab∗ ab∗ a)∗ . El diagrama de transición de un Autómata Finito es: b a b a b
a
Matemáticas Discreta
Prof. José Luis Chacón
Pensar y actuar
Trabajo VIII
Semestre A2005
Problemas
d ) Una expresión regular para este lenguaje es: b∗ ∪ b+ (ab+ )∗ . El diagrama de transición de un Autómata Finito es: b b a b
e) Una expresión regular para este lenguaje es: b∗ (ab+)∗ ∪ b∗ a(b+ a)∗ . El diagrama de transición de un Autómata Finito es: b a b
f ) Una expresión regular para este lenguaje es: ǫ ∪ (b + ǫ)(ab)∗ ∪ (a + ǫ)(ba)∗ . El diagrama de transición de un Autómata Finito es:
b b a a
1. Hallar un autómata finito que acepte el lenguaje dado a) L = {w| w contiene un número impar de a′ s y un número par de b′ s} b) L = {w| w contiene un número par de a′ sy un número par de b′ s} c) L = {w| w contiene un número impar de a′ s y un número impar de b′ s} d ) L = {w| w contiene un ab o ba como subpalabras} e) L = {w| w contiene un ab y ba como subpalabras} f ) L = {w| w contiene un ab ó ba como subpalabras, pero no ambas} 2. Solución a) Un diagrama de transición del autómata finito es:
Matemáticas Discreta
Prof. José Luis Chacón
Pensar yactuar
Trabajo VIII
Semestre A2005
Problemas
a a
b
b a
b
b
a b) Cambiando el estado de aceptación del autómata representado arriba obtenemos el autómata: a a
b
b a
b
b
a
c) De nuevo cambiando el estado de aceptación obtenemos el autómata correspondiente
a a
b
b a
b
b
a
d ) A continuación un diagrama de transición de un autómata finitodeterminista que acepta el lenguaje cuyas palabras contienen las subpalabras ab o ba o ambas Matemáticas Discreta Prof. José Luis Chacón Pensar y actuar
Trabajo VIII
Semestre A2005
Problemas
a b a b a b b
b
a
a
e) Este autómata acepta las palabras que contienen las subpalabras ab y ba a b a b a b a a a, b b b
f ) Este autómata acepta las palabras que contienen lassubpalabras ab ó ba, pero no ambas a b a b a b a a a, b b b
Ejercicios
1. Sean A = {0, 11} y B = {00, 01}. Hallar cada uno de estos conjuntos. a) AB b) BA c) A2 d) B3
2. Hallar todos los pares de conjuntos de palabras A y B para los que AB = {10, 111, 1010, 10111, 101000} Matemáticas Discreta Prof. José Luis Chacón Pensar y actuar
Trabajo VIII
Semestre A2005
Problemas
3. Describa loselementos del conjunto A∗ para los valores de A siguientes: a) {ab} b) {aaa} c) {a, ab} d) {a, aba}
4. Determine si la palabra aaaba está o no encada uno de los siguientes conjuntos: a) d) (a ∪ b)∗ (aa)∗ (ba)∗ b) a∗ b∗ a∗ e) (aaa)∗ b∗ a c) aaa∗ ba f ) (aaa ∪ bbb)(bb ∪ ba)
5. Dado el siguiente diagrama de transición
b
a b a, b a
a
b
i) Determinar las cadenas que son aceptadas ono por el autómata a) bab b) aaba b) aa∗ e) a∗ b∗ c) aaaaaab d) babababab c) ab∗ f ) a(a ∪ b)∗ c) xy + x∗ f ) (x ∪ y)(yx ∪ yxy)∗
ii) Determinar si los lenguajes dados son aceptados o no por el autómata a) (a)∗ d) (ab)∗
6. Hallar un autómata determinista que reconozca los siguientes lenguajes sobre Σ = {x, y} a) d) xyxxy x(yx)∗ y b) {xn : n > 2} e) (x ∪ y)(yx ∪ xyx)∗
7. De los lenguajes...
Semestre A2005
Problemas
Problemas de Lenguajes y Autómatas
1. Para los lenguajes dados sobre Σ = {a, b} construir una expresión regular de él y un Autómata Finito que lo acepte: a) L = {w|w tiene un numero par de a′ s} b) L = {w|w tiene un numero impar de a′ s} c) L = {w|w tiene un numero múltiplo de 3 de a′ s} d ) L = {w| toda a en w está entre dos b′ s} e) L = {w| nohay dos a′ s consecutivas en w} f ) L = {w| w no contiene la subpalabra aa ni bb} 2. Solución a) Una expresión regular que represente el lenguaje L es b∗ (ab∗ ab∗ )∗ . El diagrama de transición de un Autómata Finito es: b a b
a b) Una expresión regular para este lenguaje es: b∗ ab∗ (ab∗ ab∗ )∗ . El diagrama de transición de un Autómata Finito es: b a b
a c) Una expresión regular para estelenguaje es: b∗ (ab∗ ab∗ a)∗ . El diagrama de transición de un Autómata Finito es: b a b a b
a
Matemáticas Discreta
Prof. José Luis Chacón
Pensar y actuar
Trabajo VIII
Semestre A2005
Problemas
d ) Una expresión regular para este lenguaje es: b∗ ∪ b+ (ab+ )∗ . El diagrama de transición de un Autómata Finito es: b b a b
e) Una expresión regular para este lenguaje es: b∗ (ab+)∗ ∪ b∗ a(b+ a)∗ . El diagrama de transición de un Autómata Finito es: b a b
f ) Una expresión regular para este lenguaje es: ǫ ∪ (b + ǫ)(ab)∗ ∪ (a + ǫ)(ba)∗ . El diagrama de transición de un Autómata Finito es:
b b a a
1. Hallar un autómata finito que acepte el lenguaje dado a) L = {w| w contiene un número impar de a′ s y un número par de b′ s} b) L = {w| w contiene un número par de a′ sy un número par de b′ s} c) L = {w| w contiene un número impar de a′ s y un número impar de b′ s} d ) L = {w| w contiene un ab o ba como subpalabras} e) L = {w| w contiene un ab y ba como subpalabras} f ) L = {w| w contiene un ab ó ba como subpalabras, pero no ambas} 2. Solución a) Un diagrama de transición del autómata finito es:
Matemáticas Discreta
Prof. José Luis Chacón
Pensar yactuar
Trabajo VIII
Semestre A2005
Problemas
a a
b
b a
b
b
a b) Cambiando el estado de aceptación del autómata representado arriba obtenemos el autómata: a a
b
b a
b
b
a
c) De nuevo cambiando el estado de aceptación obtenemos el autómata correspondiente
a a
b
b a
b
b
a
d ) A continuación un diagrama de transición de un autómata finitodeterminista que acepta el lenguaje cuyas palabras contienen las subpalabras ab o ba o ambas Matemáticas Discreta Prof. José Luis Chacón Pensar y actuar
Trabajo VIII
Semestre A2005
Problemas
a b a b a b b
b
a
a
e) Este autómata acepta las palabras que contienen las subpalabras ab y ba a b a b a b a a a, b b b
f ) Este autómata acepta las palabras que contienen lassubpalabras ab ó ba, pero no ambas a b a b a b a a a, b b b
Ejercicios
1. Sean A = {0, 11} y B = {00, 01}. Hallar cada uno de estos conjuntos. a) AB b) BA c) A2 d) B3
2. Hallar todos los pares de conjuntos de palabras A y B para los que AB = {10, 111, 1010, 10111, 101000} Matemáticas Discreta Prof. José Luis Chacón Pensar y actuar
Trabajo VIII
Semestre A2005
Problemas
3. Describa loselementos del conjunto A∗ para los valores de A siguientes: a) {ab} b) {aaa} c) {a, ab} d) {a, aba}
4. Determine si la palabra aaaba está o no encada uno de los siguientes conjuntos: a) d) (a ∪ b)∗ (aa)∗ (ba)∗ b) a∗ b∗ a∗ e) (aaa)∗ b∗ a c) aaa∗ ba f ) (aaa ∪ bbb)(bb ∪ ba)
5. Dado el siguiente diagrama de transición
b
a b a, b a
a
b
i) Determinar las cadenas que son aceptadas ono por el autómata a) bab b) aaba b) aa∗ e) a∗ b∗ c) aaaaaab d) babababab c) ab∗ f ) a(a ∪ b)∗ c) xy + x∗ f ) (x ∪ y)(yx ∪ yxy)∗
ii) Determinar si los lenguajes dados son aceptados o no por el autómata a) (a)∗ d) (ab)∗
6. Hallar un autómata determinista que reconozca los siguientes lenguajes sobre Σ = {x, y} a) d) xyxxy x(yx)∗ y b) {xn : n > 2} e) (x ∪ y)(yx ∪ xyx)∗
7. De los lenguajes...
Leer documento completo
Regístrate para leer el documento completo.