Matediscretas

Solo disponible en BuenasTareas
  • Páginas : 5 (1204 palabras )
  • Descarga(s) : 0
  • Publicado : 12 de mayo de 2011
Leer documento completo
Vista previa del texto
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...
tracking img