12/09/13 Campus13 2013-2

66.165.175.211/campus13_20132/mod/quiz/attempt.php?id=49419 1/3

1

Puntos: 1

Seleccione al menos

una respuesta.

a. El lenguaje de las cadenas equilibradas con igual número de 0´s y de 1´s tales que ningún prefijo de cualquiera de ellas posee

más de dos 0´s que 1´s ni más de dos 1´s que 0´s es un lenguaje regular.

b. No existe ningún autómata determinista que reconozca el lenguaje de las cadenas en las que toda pareja de 0´s contiguos

aparece antes de cualquier pareja de 1´s contiguos.

c. Si L es un lenguaje regular también lo es el lenguaje consistente en las inversas de las cadenas de L

d. El lenguaje de las cadenas con a lo sumo una pareja de 0´s consecutivos y a los sumo una pareja de 1´s consecutivos no es

regular.

Indique cuál de las siguientes afirmaciones referidas a lenguajes del alfabeto ∑ = {0,1,2} son ciertas:

2

Puntos: 1

Seleccione al menos

una respuesta.

a. Hay palabras como “ba”, que no tienen a´s seguidas y sin embargo no son aceptadas por el AFD

b. Tiene dos f inales o de aceptación q1 y q2 .

c. Hay palabras como “baa”, que tiene a´s seguidas y sin embargo son aceptadas por el AFD.

d. Hay palabras como “baba” que no tienen a´s seguidas y sin embargo son aceptadas por el AFD pero que no pertenecen al

alfabeto dado.

Se diseña el siguiente Autómata Finito Deterministico (AFD) para el lenguaje de palabras delalfabeto {a,b} que no tiene varias a´s seguidas. Esta solución es defectuosa porque.

3

Puntos: 1

Seleccione al menos

una respuesta.

a. 2. Ambos autómatas reconocen el mismo lenguaje incluyendo la cadena vacía.

b. 3. El autómata A es más potente por ser No Determinista.

c. 4. Cualquier autómata no determinista que reconozca el mismo lenguaje que el autómata B tiene al menos cuatro estados.

d. 1. Los autómatas reconocen el lenguaje formado por todas las cadenas que empiezan por 1 y que no terminan en dos ceros

consecutivos.

1. Indique cual de las siguientes afirmaciones referidas a los autómatas de la figura, son

ciertas. (Observe que hay una transición lambda que no lee ningún símbolo de la cadena deentrada):

4

Puntos: 1

La expresión regular que se asocia la siguiente autómata es:

Act 4: Lección Evaluativa Unidad No.1

AUTOMATAS Y LENGUAJES FORMALES Perfil Salir

12/09/13 Campus13 2013-2

66.165.175.211/campus13_20132/mod/quiz/attempt.php?id=49419 2/3

Seleccione una

respuesta.

a. r = (1)* + (0) + lambda

b. r = (10) * + 1*

c. r = (10 + 0) *

d. r = (1 + 0) + 1*

5

Puntos: 1

Seleccione una

respuesta.

a. La equivalencia de un AFD y un AFND se da solo evaluando el tipo de símbolos que componen el alfabeto.

b. Un AFD es equivalente a un AFND si el número d etransiciones es igual, independiente del número de estados.

c. os autómatas f initos determinísticLos (AFD) son un subconjunto propio de los no determinísticos (AFN)

d. La equivalencia de un AFND y un AFD, obliga a que tengan el mismo número de estados

Cuando se habla de equivalencia de autómatas finitos determinísticos y autómatas finitos no determinísticos, es válido afirmar:

6

Puntos: 1

Seleccione una

respuesta.

a. Todo Autómata por defecto es Determinístico.

b. Para covertir u AFD a u AFND, el AFD debe tener menos estados que el AFND

c. Todo Autómata por defecto es No determinístico

d. Los autómatas f initos determinísticos (AFD) son un subconjunto propio de los no determinísticos (AFN)

Acerca de la Equivalencia de AFD Y AFN es válido afirmar.

7

Puntos: 1

Seleccione una

respuesta.

a. Ninguna de las afirmaciones anteriores es cierta

b. Los autómatas f initos tienen un número f inito de estados.

c. Los autómatas f initos sólo pueden aceptar lenguajes f initos.

d. Las máquinas de Turing y los autómatas de pila son autómatas f initos

Indique cuál de las siguientes afirmaciones se apropia a los conceptos de los Autómatas Finitos:

8

Puntos: 1

Seleccione una

respuesta.

a. No representa un autómata válido por que tiene un solo estado.

b. Un Autómata que acepta palabras o cadenas que contienen únicamente b´s

c. No representa un autómata válido por que el mismo estado inicial es el mismo estado f inal.

d. Un Autómata de tipo AFND válido

Que representa la siguiente figura:

9

Puntos: 1

Seleccione una a. No hay número mínimo

El número mínimo de estados de un autómata finito no determinista es:

Tiempo restante

0:41:02

12/09/13 Campus13 2013-2

66.165.175.211/campus13_20132/mod/quiz/attempt.php?id=49419 3/3

respuesta. b. Dos

c. Depende del alfabeto sobre el que está definido.

d. Uno

10

Puntos: 1

Seleccione una

respuesta.

a. Es un Autómata f inito (AF)

b. Es un palíndromo

c. Es un símbolo y no es parte de un lenguaje

d. No es una cadena sino un símbolo

Acerca de la cadena vacía lambda se puede afirmar que:

Guardar sin enviar Enviar todo y terminar

Usted se ha autentificado como JA NES SA ENZ (Salir)

301405A

Campus13 2013-II ► 301405A ► Cuestionarios ► Act 4: Lección Evaluativa Unidad No.1 ► Intento

1