Examen Automatas

1. Una de las operaciones que permiten las “Expresiones Regulares” es el “Cierre u operación
estrella”. Si  es una expresión regular, entonces * es una expresión regular que denota
{*}. Es decir denota las cadenas
A.
B.
C.
D.

,,,,,…
,,,,…,
,,,,…
,,,,,…

2. En el siguiente diseño de máquina de Turing (MT), identifiquecuales operaciones realiza y
que son válidas acordes a la forma de “operar” o “trabajar” una MT:

A. Inicialización de la máquina. Al principio, la cinta está vacía. Se pone la unidad de control
en el estado inicial y se posiciona la cabeza sobre la primera letra de la cadena introducida
y se posiciona la cabeza sobre la primera letra de la cadena introducida. A continuación se
introduce lacadena de entrada, por ejemplo abaa$abaa.
B. Inicialización de la máquina. Al principio, la cinta está en blanco. A continuación se
introduce la cadena de entrada, por ejemplo abaa$abaa, se pone la unidad de control en
el estado inicial y se posiciona la cabeza sobre la primera letra de la cadena introducida.
C. Inicialización de la máquina. Al principio la cinta contiene la cadena abaa$abaa,se pone la
unidad de control en el estado inicial y se posiciona la cabeza sobre la primera letra de la
cadena introducida. Se da inicio a la máquina para que lea celda por celda.
D. Inicialización de la máquina. Al principio la cinta contiene la cadena abaa$abaa. Se recorre
toda la cinta para identificar el estado inicial y final. Se posiciona la cabeza en el estado
inicial. Se recorre lacinta.
3. Partiendo de la definición de que un Autómata Finito Determinístico (AFD) está dado por
la quíntupla A = (Q, , f, q0, F) donde:






Q es un conjunto de estados
 es el alfabeto de entrada
f: Q   → Q es la función (total) de transición
q0  Q es el estado inicial
F  Q es el conjunto de estados finales

Y que para el ejercicio, el autómata acepta las cadenas (01) *1):
A = ({q0, q1, q2, q3}, {0, 1), f, q0, {q2,})
Representado mediante el grafo:

La tabla de transición correspondiente es:

A
→q0
q1
*
q2
q3

A
0
q0
q0
q3
q2

A
→q0
q1
q2
*q3

C
0
q1
q3
q3
q3

1
q1
q0
q0
q2

1
q0
q0
q3
q3

A
→q0
q1
*
q2
q3

B
0
q1
q3
q3
q3

1
q2
q0
q3
q3

A
→q0
q1
*
q2
q3

D
0
q0
q3
q0
q2

1
q0
q1q3
q2

4. Acorde al autómata del ejercicio N 3, el nombre “finito” proviene de
A. Que el autómata tiene un solo estado inicial que se puede representar por un * o por un
circulo doble
B. Que el autómata contiene un alfabeto símbolos (letras del abecedario) y estas son finitas
C. Del hecho que el autómata solo tiene un conjunto finito de estados distintos para recordar
lo procesado (notiene ningún sistema de almacenamiento de información adicional).
D. Del hecho que el autómata almacena información en un solo estado (el final), que es
donde termina su recorrido
5. Para el siguiente autómata finito denotado como: A2 = (E, Q, f, q1, F) donde E = {0,1}, F =
{q2} y Q = {q1, q2, q3, q4}, identifique correctamente el Lenguajes que genera y la expresión
regular

A.
B.
C.
D.L = {A2} = {0, 001, 01111, …} = {1(10)n /n ≤ 0}
L = {A2} = {1, 101, 10101, …} = {1(01)n /n ≥ 0}
L = {A2} = {0, 111, 11100, …} = {1(10)n /n = 0}
L = {A2} = {0, 001, 00100, …} = {1(01)n /n ≠ 0}

La expresión regular es: 0(01)*
La expresión regular es: 1(01)*
La expresión regular es: 1(01)+
La expresión regular es: 1(01)*

6. El siguiente diagrama de Moore representa:

A.
B.
C.
D.Expresión regular (q|q1)*
Expresión regular (ac|b)*
Expresión regular (bb|ab)*
Expresión regular (ac|b|b)*

7. Un árbol de derivación está conformado por una serie de componentes, identifique los
correctos en las siguientes opciones
A.
B.
C.
D.

Nodo raíz, nodos interiores, hojas
Nodo principal, nodos secundarios, nodos finales
Nodo inicial, nodos interiores, nodo final
Nodo...