Automatas

TEORÍA DE AUTÓMATAS I
Informática de Sistemas
Soluciones a las cuestiones de examen del curso 2007/08
Febrero 08, 1ª semana
1. Indique cuál de las afirmaciones siguientes es FALSA:
a) Un autómata finito determinista utilizado como reconocedor de lenguajes con al
menos una cadena necesariamente tiene que tener al menos un estado de aceptación
b) Dada una gramática regular G, siempre existeun autómata finito M tal que L(G) =
L(M) y M tiene un único estado de aceptación
c) Un autómata reconoce una cadena cuando alcanza un estado de aceptación durante
su lectura
Solución: C. Para que una cadena sea aceptada por autómata finito o de pila es
necesario que la lectura del último símbolo de la cadena le conduzca a un estado de
aceptación. A es trivialmente verdadera. B es verdadera:dado un autómata finito,
siempre es posible convertirlo en otro que tenga un único estado de aceptación y que
acepte el mismo lenguaje (véase el problema 26 del libro de texto).
2. Indique cuál de los siguientes lenguajes NO es regular:
a) L ={anbm ⏐ n+m > 5, n > 0, m ≥ 0}
b) L ={anbm ⏐ m > 5n, n > 0}
c) L ={an ⏐ n/10 es un entero}
Solución: B. En el caso de los lenguajes A y C loslenguajes pueden representarse
mediante las expresiones regulares {aaaaaaa*b* ∪ aaaaaa*bb* ∪ aaaaa*bbb* ∪
aaaa*bbbb* ∪ aaa*bbbbb* ∪ aa*bbbbbbb*} y {aaaaaaaaaa}*, respectivamente.
La demostración de que el lenguaje B no es regular es análoga a demostración de que
no lo es el lenguaje {anbn}.
3. Sean L1 y L2 los lenguajes aceptados, respectivamente, por los autómatas de las
figuras 1) y 2). Indiquecuál de las siguientes afirmaciones es cierta:
a) L1 = L2, uno de los dos autómatas es determinista y el otro no lo es.
b) L1 = L2, si consideramos que uno de los diagramas está incompleto.
c) L1 ≠ L2
F ig . 1

b

F ig . 2

a

a
b

a

b

b

a

a
b

b

a

b
b

b

2

Solución: C. El autómata de la figura 2 no acepta la cadena abb, mientras que el de la
figura 1)sí la acepta.
4. Indique cuál de las siguientes gramáticas genera el lenguaje L = {amb2mc2n ⏐ m >0, n
≥ 0}
a) S → AB, A → aAb | ab, B → bBc | λ
b) S → AB, A → aAbb | abb, B → cBc | λ
c) Las dos gramáticas anteriores generan el lenguaje L
Solución: B. La gramática del apartado A genera el lenguaje L = {anbmcp ⏐m = n+p, n
> 0, p ≥ 0}. A la vista de las reglas de la gramática B es evidente quegenera el
lenguaje indicado (por cada a se generan dos b’s; el número de c’s es arbitrario pero
necesariamente par).
5. Considere el lenguaje 2-menos(L) = {w | vw ∈ L y |v| = 2}, v, w ∈ ∑*, ∑= {a,b}.
Indique cuál de las siguientes afirmaciones es FALSA.
a) Si L es un lenguaje regular entonces 2-menos(L) es regular
b) Aunque L sea regular, es posible que 2-menos(L) no sea regular
c) Aunque Lno sea regular 2-menos(L) puede ser regular
Solución: B. A es verdadera: el autómata finito que reconoce 2-menos(L) puede
construirse fácilmente a partir del autómata que reconoce a L sin más que añadir un
nuevo estado de inicio con arcos etiquetados por λ hacia todos los estados
alcanzables mediante un camino de longitud 2 desde el estado inicial del autómata de
partida. De ahí se deduce queB es falsa. C es verdadera: considere L el lenguaje
cuyos dos primeros símbolos indican si la longitud total de la cadena es un número
primo (p.e. aa indica que la longitud de la cadena es un número primo y bb que no es
un número primo); en este caso: 2-menos(L) = ∑*, lenguaje regular.
6. Indique cuál de las siguientes afirmaciones, referidas a la estrella de Kleene de un
conjunto, es FALSA:a) La estrella de Kleene de un alfabeto Σ, Σ *, es el lenguaje de todas las cadenas que
se pueden formar con símbolos de Σ, incluyendo la cadena vacía.
b) x ∈ Σ * significa que x es una cadena formada con símbolos de Σ, o bien la cadena
vacía
c) La estrella de Kleene de un conjunto siempre es un conjunto infinito
Solución: C. A y B son ciertas por definición. C es falsa, ya que si el...