simulacro_301405

VICERRECTORÍA DE MEDIOS Y MEDIACIONES PEDAGÓGICAS VICERRECTORÍA ACADÉMICA Y DE INVESTIGACIÓN SISTEMA NACIONAL DE EVALUACIÓN ESCUELA DE CIENCIAS BÁSICAS, TECNOLOGÍA E INGENIERÍA

CONVOCATORIA NACIONAL

I – 2012

CURSO: AUTOMATAS Y LENGUAJES FORMALES CÓDIGO: 301405

TEMA A

AUTOR: Carlos Alberto Amaya Tarazona NODO: TUNJA CEAD DUITAMA Página 1 de 11

CUADERNILLO DE ÍTEMS

ÍTEMS DE SELECCIÓN MÚLTIPLE CON ÚNICA RESPUESTA A continuación, usted encontrará preguntas que se desarrollan en torno a un enunciado, problema o contexto, frente al cual, usted debe seleccionar aquella opción que responda correctamente al ítem planteado entre cuatro identificadas con las letras A, B, C, D. Una vez la seleccione, márquela en su hoja de respuestas rellenando el óvalo correspondiente. 1. Se denomina estrella de Kleene, cierre reflexivo transitivo u operación asterisco sobre un alfabeto

∑ al conjunto de todas las cadenas que se pueden construir a partir de los símbolos del alfabeto ∑; en notación matemática esta definición se expresa así.

Dado el alfabeto: ∑= {a,b} una representación válida de la expresión regular y su lenguaje sería:

A. Expresión Regular: ; Como Lenguaje: { Ø,b,bbb,bbbbbb,…}

B. Expresión Regular: ; Como Lenguaje: empiezan en a y terminan en ba

C. Expresión Regular: ; Como lenguaje: {a,aa,ab,aaa,aab,aba,abb, …}

D. Expresión Regular: . ; Como Lenguaje: empiezan en a y terminan en b

2. Se denomina cadena, palabra o frase a una secuencia finita de símbolos de un alfabeto ∑. Estas

cadenas son denotadas como w. Dado el siguiente autómata finito determinístico (AFD) A = (Q, ∑, f, q0 , F) donde:

• Q es un conjunto de estados. • ∑ es el alfabeto de entrada • f: Q X ∑ → Q es la función (total) de transición. • q 0 ∈ Q es el estado inicial.

• F ⊆ Q es el conjunto de estados finales.



I – 2012


TEMA A


Y que para el ejercicio ∑ = {a,b} Q ={ q 0 , q 1 } F = {q1 } se representa mediante el siguiente diagrama de Moore:

El conjunto de palabras aceptadas por este autómata son:

A. {w a | w ϵ {a,b}2

}

B. {w a | w ϵ {a,b} * } C. Todas las palabras que terminan en a y que estén precedidas por una b D. Todas las palabras que terminan en dos a´s

3. Se construyó el siguiente autómata finito M para que cumpliera:

L(M) = {x m y n z p | m,n y p son enteros no negativos }

Pero no fue válido por que:

A. Tiene dos estados de aceptación o finales. B. No acepta las cadenas {xyz} {yz} {xxxy} C. No acepta las cadenas {x} {xxxzzz} {z} D. Acepta solo las cadenas que combinen los elementos {x,z} del alfabeto



I – 2012


TEMA A


4. Para el autómata del ejercicio anterior, (ejercicio 3) determine que afirmación es válida si se presenta la siguiente gramática. Para el análisis, asigne un nombre a los estados del autómata que apliquen a la gramática dada.

S → xS S → yA S → zB A → yA A → yB B → zB B → λ

A. El autómata y la gramática son equivalentes B. El autómata y la gramática no definen un estado de aceptación. C. La gramática no referencia ningún estado ni transición válida del autómata. D. No es equivalente el autómata con la gramática ya que la gramática no genera la cadena vacía.

5. Para el siguiente autómata finito determinístico (AFD), identifique que afirmaciones son válidas para

la expresión: Tenga en cuenta que se denomina cadena, palabra o frase a una secuencia finita de símbolos de un alfabeto ∑. Estas cadenas son denotadas como w.

A. Reconoce las palabras sobre a,b que terminan en un número par de a´s contiguas B. Reconoce solo las frases sobre a,b que empiezan por b C. Reconoce las palabras sobre a,b que tienen un número par de a´s contiguas. D. Reconoce solo las cadenas sobre a,b que empiezan por a

6. Sea el alfabeto ∑ = {0,1} y el autómata de la figura:



I – 2012


TEMA A


Para el ejercicio analice la cadena sin tener en cuenta si es válida o no. (aceptada o no aceptada) Determine cuál interpretación es válida al analizar la cadena 00101

A. El autómata puede procesar la cadena 00101 de 4 formas distintas. B. Sólo existe un modo en el que el autómata puede procesar la cadena 00101. C. Al procesar la cadena 00101, el último estado visitado es siempre el estado 3 o bien el estado 2. D. Se generan miles cadenas 00101 ya que el autómata es infinito.

7. Al combinar los diagramas de transiciones de las siguientes máquinas M 1 y M 2 :

Para formar el diagrama de transiciones de la máquina compuesta por: Da como solución la siguiente máquina M.

El funcionamiento correcto de la máquina M es.

A. Busca el primer símbolo distinto de x / Si ese símbolo es y; lo cambia por otra y / Regresa a uno (1).

B. Busca el primer símbolo distinto de y / Si ese símbolo es x; lo cambia por otra x / Regresa a cuatro (4).

C. Busca el primer símbolo distinto de x / Si ese símbolo es y; lo cambia por una x / Regresa a dos (2) para evaluar la memoria y finalizar en h (halt).

D. Busca el primer símbolo distinto de y / Si ese símbolo es x; lo cambia por una y / Regresa a uno (1).



I – 2012


TEMA A


ÍTEMS DE SELECCIÓN MÚLTIPLE CON MÚLTIPLE RESPUESTA Este tipo de preguntas consta de un enunciado, problema o contexto a partir del cual se plantean cuatro opciones numeradas de 1 a 4, usted deberá seleccionar la combinación de dos opciones que responda adecuadamente a la pregunta y marcarla en la hoja de respuesta, de acuerdo con la siguiente información: Marque A si 1 y 2 son correctas. Marque B si 1 y 3 son correctas. Marque C si 2 y 4 son correctas. Marque D si 3 y 4 son correctas. 8. Indique cual de las siguientes afirmaciones referidas a los autómatas de la figura, son ciertas.

(Observe que hay una transición λ que no lee ningún símbolo de la cadena de entrada):

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

2. Ambos autómatas reconocen el mismo lenguaje incluyendo la cadena vacía. 3. El autómata A es más potente por ser No Determinista. 4. Cualquier autómata no determinista que reconozca el mismo lenguaje que el autómata B

tiene al menos cuatro estados. 9. Sean L 1 el lenguaje generado por la gramática G 1 y L 2 el lenguaje generado por la gramática G 2

S → xABy A → xzS | B B → yz | λ

S → xAyzy | xAy A → xzS | yz | λ

Gramática G1 Gramática G 2



I – 2012


TEMA A


Indique cual de las siguientes afirmaciones es cierta (donde ⊂ denota la inclusión estricta):

1. Mediante G1 se puede generar todas las cadenas de L 2 2. Las gramáticas son idénticas 3. Las gramáticas generan el mismo lenguaje. 4. Las gramáticas son distintas, y L1 ⊂ L 2

10. Las gramáticas del ejercicio anterior (ejercicio 9), tienen dos particularidades que son válidas

afirmarlas:

1. Las reglas de las gramáticas difieren por que tienen diferentes terminales. 2. La palabra generable por la gramática G1 y G 2 es xxzyzy 3. La palabra generable por la gramática G1 y G 2 es xyzyzy 4. La lista de reglas están denotadas de forma comprimida.

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

1. 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.

2. 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.

3. 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.

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

12. Con referencia a la funcionalidad y creación de una Máquina Universal de Turing (MUT), es válido

afirmar:

1. Una Máquina Universal de Turing es capaz de decidir cualquier lenguaje independiente del contexto.

2. En el estado de parada de una MUT no puede salir ningún arco 3. En una MUT el lenguaje aceptado por esta máquina no puede contener una cadena vacía. 4. La MUT se diseñó para realizar cálculos específicos.



I – 2012


TEMA A


13. Tome como válida la ER (Expresión Regular) α = a + bc + b 3 a ¿Cuál es el lenguaje descrito por α? Y ¿Qué expresión regular corresponde al lenguaje universal sobre el alfabeto {a,b,c}?

1. L (α) = {a, bc, bbba} y es un lenguaje infinito no deterministico sobre la cadena {a,b,c} 2. L (α) = {a, bc, bbba} y es un lenguaje finito sobre el alfabeto {a,b,c} 3. La expresión regular (ER) que describe el lenguaje universal sobre este alfabeto es

(a+b)*

+c 4. La expresión regular (ER) que describe el lenguaje universal sobre este alfabeto es

(a+b+c)*

ÍTEMS DE ANÁLISIS DE RELACIÓN Este tipo de ítems consta de dos proposiciones así: una Afirmación y una Razón, unidas por la palabra PORQUE. Usted debe examinar la veracidad de cada proposición y la relación teórica que las une. Para responder este tipo de ítems, debe leerla completamente y señalar en la hoja de respuesta, la elegida de acuerdo con las siguientes instrucciones: Marque A si la afirmación y la razón son VERDADERAS y la razón es una explicación CORRECTA de la afirmación. Marque B si la afirmación y la razón son VERDADERAS, pero la razón NO es una explicación CORRECTA de la afirmación. Marque C si la afirmación es VERDADERA, pero la razón es una proposición FALSA. Marque D si la afirmación es FALSA, pero la razón es una proposición VERDADERA. 14. Dado el siguiente autómata:

El conjunto de cadenas que es capaz de aceptar este autómata es {b,bb,bbb} PORQUE este AFD está compuesto por un símbolo b que converge a tres estados de aceptación q 3 , q 4 y q 5 y a un estado final q 5 .



I – 2012


TEMA A


15. El autómata representado en el ejercicio catorce (14), corresponde a un AUTOMATA FINITO NO DETERMINISTA CON LANDA TRANSICIONES (AFND - λ) al que se le permite cambiar de estado sin necesidad de consumir o leer un símbolo de entrada PORQUE cumple con uno de los requisitos para no ser determinista cuando al analizar el autómata en el estado q 1 en un cierto instante y si el símbolo actual es b, en el instante siguiente, el autómata puede decidir de forma no determinista entre “leer el símbolo b y cambiar al estado q 4 ”, o bien, “cambiar al estado q 2 sin mover el cabezal de lectura”.

16. La concatenación de lenguajes L 1 y L 2 es otro lenguaje que contiene todas las palabras que se

pueden construir concatenando una palabra de L 1 con una palabra de L 2 . Dado dos Lenguajes L 1 y L 2 entonces L1 L 2 ≠ L 2 L 1 PORQUE La concatenación de lenguajes es conmutativa.

17. La mejor forma de implementar un autómata que considere el lenguaje de los PALINDROMOS (palabras que se leen igual al derecho y al revés como larutanosaportootropasonatural) es con un autómata de Pila (AP) PORQUE esta máquina (AP) ofrece un almacenamiento auxiliar llamado Pila que permite recordar o almacenar los estados y el contenido y situación de los mismos evaluando carácter por carácter arbitrarios con tamaños y cadenas grandes.

18. Las máquinas de Turing (MT) son más de propósito específico que cualquier otro Autómata Finito (AF) y cualquier Autómata de Pila (AP) PORQUE estas MT pueden reconocer tanto los lenguajes regulares como los lenguajes independientes del contexto y, además, muchos otros tipos de lenguajes.

19. Se llama “clase de lenguajes” a conjuntos de alfabetos que comparten una cierta propiedad dada. La clasificación de lenguajes en “clases de lenguajes” es debida a N. Chomsky, quién propuso una jerarquía de lenguajes, donde las clases más complejas incluyen a las más simples. Dentro de esta clasificación propuesta están los “Lenguajes Regulares” que es la clase más compleja o grande de la jerarquía PORQUE Los Lenguajes Regulares incluye a los lenguajes más simples. Un ejemplo de Lenguaje Regular es el conjunto de todos los números binarios.

ÍTEMS DE ANÁLISIS DE POSTULADOS Los ítems que encontrará a continuación constan de una afirmación VERDADERA (tesis) y dos postulados también VERDADEROS, identificados con POSTULADO I y POSTULADO II. Usted debe analizar si los postulados se deducen lógicamente de la afirmación y seleccionar la respuesta en su hoja de cotejo, conforme a la siguiente instrucción:



I – 2012


TEMA A


Marque A si de la tesis se deducen los postulados I y II. Marque B si de la tesis se deduce el postulado I. Marque C si de la tesis sólo se deduce el postulado II. Marque D si ninguno de los postulados se deduce de la tesis.

20. TESIS: Los AF (Autómatas Finitos) pueden considerarse como mecanismos aceptadores o reconocedores de palabras

POSTULADO I. Un AF es una máquina sin memoria externa; son los estados los que resumen de alguna forma la información procesada. POSTULADO II. De manera informal se puede decir que un Autómata Finito aceptará una palabra de entrada si, comenzando por un estado especial llamado estado inicial y estando la cabeza de lectura apuntando al primer símbolo de la cadena, la máquina alcanza un estado final o de aceptación después de leer el último símbolo de la cadena

21. TESIS: La definición de palabra vacía λ se puede obtener partiendo de: Dado un alfabeto ∑, entonces λ se define como la única palabra construida con cero (0) símbolos del alfabeto.

POSTULADO I. Aunque se presente por un carácter simple, es una palabra, mas no un símbolo del alfabeto, es decir: λ ∉ ∑

POSTULADO II. Todas las palabras que pueden formarse con los símbolos del alfabeto ∑*

se caracterizan por:

• Contener un número infinito de palabras. • Una palabra puede estar conformada por solo un símbolo del alfabeto.

22. TESIS: Con los símbolos del alfabeto ∑ se forman cadenas, frases o palabras que se denotan por la letra ω. Algunas operaciones entre palabras son la concatenación y la inversa. La concatenación por ejemplo no tiene la propiedad conmutativa, es decir: ω1ω 2 ≠ ω 2 ω 1 . Una situación particular que se da al formar palabras, es la de crear “palíndromos” que son aquellos que toman por unidad la letra, es decir, cuya última letra es la misma que la primera, la penúltima es la misma que la segunda, etc.



I – 2012


TEMA A


POSTULADO I. La Inversión (ω R ) consiste en una operación sobre palabras o cadenas que escribe al revés una palabra. La palabra resultante se denomina inversa. En general (ω1 ω 2 ) R ≠ ω 1

R ω 2R pero (ω1ω 2 ) R = ω 2

R ω 1R

POSTULADO II. El Palíndromo se puede definir como: (ω = ω R ).

Ejemplo: ω = reconocer 23. TESIS: Cuando se tratan los PROBLEMAS INSOLUBLES PARA LA TEORIA DE LENGUAJES, se

presentan los “Problemas de decisión” (PD). Un PD es aquél formulado por una pregunta (referida a alguna propiedad) que requiere una respuesta de tipo “si/no”. Hay problemas de decisión de tipo “soluble”, “parcialmente soluble” e “insoluble”.

POSTULADO I. Hay lenguajes formados por cadenas tales que una Máquina de Turing (MT) logra un estado final con las cadenas que reconoce y acepta solamente. POSTULADO II. Mientras que los lenguajes computables son una infinidad numerable, los lenguajes no computables son una infinidad no numerable. 24. TESIS: El siguiente diagrama define unas relaciones propias de la Teoría de autómatas y lenguajes

formales que son verdaderas. Analícelas y determine que postulados podemos deducir de la gráfica.



I – 2012


TEMA A


POSTULADO I. La Gramática describe la estructura de un lenguaje, proporcionando las reglas que determinan las combinaciones válidas de los símbolos del alfabeto que reconoce ese lenguaje. POSTULADO II. El autómata son mecanismos o máquinas abstractas que son dispositivos teóricos capaces de recibir, procesar y transmitir información (cadenas de lenguaje). 25. TESIS: Una Máquina de Turing (MT) se puede comportar como un aceptador de lenguaje, de la

misma forma que lo hace un Autómata finito (AF) o un Autómata de Pila (AP) así: Colocando una cadena ω en la cinta, situando la cabeza de lectura/escritura sobre el s ímbolo del extremo izquierdo de la cadena ω y al poner en marcha la máquina a partir de su estado inicial. Entonces ω es aceptada si, después de una secuencia de movimientos, la MT llega a un estado final y para.

POSTULADO I. Se pueden combinar dos Máquinas de Turing (MT) permitiendo que compartan la misma cinta y, que cuando una termine su ejecución, la otra empiece. POSTULADO II. Para rechazar una cadena que no es aceptable, lo único que hay que hacer es evitar que se llegue a un estado final.

simulacro_301405

Documents