UNAH * Depto.
de Matemtica Aplicada * MM-420 Matemtica Discreta Secc 1400 1700 1-2017
Ejercicios obligatorios Tarea Num 3.
(En total sern 40 ejercicios BIEN HECHOS Y MUY BIEN PRESENTADOS)
1. Sea el alfabeto = { a, b, c, d} y el lenguaje A contenido en U UU tal
que toda cadena de A tiene el prefijo b. Determine:
i) Cuntas cadenas de A tienen la subcadena propia adc
ii) Cuntas cadenas de A tiene la subcadena propia bc
2. Sean = { 0 , 1 } , L = U n para n = 0,1, 5 y los lenguajes A, B, C contenidos en L
A = { 0, 00, 000, 111, 1111, 11111} B = { w : 2 ||w|| } B = { w : ||w|| 2 }
Determine los lenguajes A B , B C , B C , A U B , A C
3. Dado = { 0 , 1 } , A es el lenguaje en + con cadenas que empiezan y terminan con
1, y pueden tener a lo ms un 0. Defina A
i) Como una concatenacin de otros lenguajes
ii) Recursivamente
4. Sea = { a, b, c } , A es el lenguaje sobre este alfabeto de cadenas no vacas con un
nmero impar de letras. Defina A
i) Como una concatenacin de otros lenguajes
ii) Recursivamente
5. Sean = { a, b, c }, A un lenguaje sobre + tal que toda cadena de A es un
palndromo. Defina A de manera recursiva.
6. A continuacin una tabla representativa de una M.E.F.
A B 00 01 10 11 A B 00 01 10 11
S0 S1 S3 S0 S1 S3 S4 000 001 010 011 100 101
S1 S0 S0 S1 S1 S0 S2 110 111 001 011 101 111
S2 S2 S3 S4 S2 S3 S4 111 110 101 100 011 010
S3 S3 S3 S3 S4 S4 S4 001 000 111 000 010 101
S4 S4 S3 S2 S2 S3 S4 110 011 001 100 101 010
i) Identifique el conjunto de estados, el alfabeto de entrada y el de salida
ii) Dibuje el diagrama de estados
iii) Aplique las funciones n, w a las cadenas 1110000010 y A11B10B0100
iv) Determine si existe una submquina o si hay estados de transicin.
7. Con = { 0, 1 } con alfabeto de entrada y de salida, construya una mquina de
estados finitos de 5 estados, de tal manera que s2 sea un estado de transicin. Que
los estados s3, s4, s5 formen una submquina de estados finitos y que s3 sea un
estado sumidero.
8. Dado = { a,b,c }, disee un reconocedor de secuencias para la subcadena: ababa
9. Sean Ai todos los subconjuntos de U = { 0, 1, 2 }, sea V = { Ai | i = 1,.. 8} E es el
conjunto de pares ordenados (Ai, Aj) donde Ai es subconjunto de Aj. Considere el
grafo dirigido G = (V, E).
i) Dibuje la grfica correspondiente al dgrafo.
ii) Encuentre todos los caminos entre A1 = y A8 = { 0, 1, 2 }
iii) Identifique si hay nodos de transicin, sumideros y aislados.
iv) Determine si hay circuitos (o ciclos)
10. Sean V = { a, b, c, d, e, f, g } E = { {a},{a,b},{a,c},{b,e},{c,d},{d,g},{d,f},{f,g} }
para obtener el grafo (no dirigido) G = (V,E)
i) Dibuje la grfica del grafo (recuerde que los nodos se representan por diminutos
crculos rellenos, a diferencia de la grfica de estados de las M.E.F.)
ii) Dibuje un grafo distinto pero isomorfo
iii) Encuentre caminos cerrados en el grafo
iv) Encuentre circuitos en el grafo
v) Determine si el grafo es conexo o no
vi) Encuentre el nmero de componentes del grafo
vii) Encuentre subgrafos de G y dibuje las grficas
viii) Encuentre un grafo encubridor de G con ms componentes
ix) Encuentre el grafo complementario de G (graficndolo)
Recurdese que es necesario NO limitarse al tipo de ejercicios de esta gua y que es
obligatorio leer y estudiar todas las secciones del texto que se han tratado en el curso.
Existen ciertas observaciones y agregados del texto que no se detallaron en clase,
pero cuyo estudio independiente es responsabilidad del estudiante.
