Teoria de Automatas

En el análisis léxico se busca reconocer cadenas. v. f.

Un autómata se puede representar a través de una gramática. v. f.

Un autómata se puede representar a través de una expresión regular. v. f.

Un alfabeto es un conjunto de palabras. v. f.

Una cadena es un componente de un alfabeto. v. f.

Con la cadena vacía se puede formar un símbolo. v. f.

La longitud de una cadena es igual a la cantidad de símbolos dealfabeto con que se forma la cadena. v. f.

Un lenguaje se conforma por un conjunto finito de símbolos. v. f.

Un lenguaje es un conjunto de símbolos. v. f.

El siguiente gráfico, ¿qué expresión regular representa?. a | b. ab. a+b+. a*b*.

El siguiente gráfico, ¿qué expresión regular representa?. (a|b)+c. (a+b+)c. (a|b+)c. (ab+c).

El siguiente gráfico, ¿qué expresión regular representa?. (a b )*. (a b*). (a* b). (a|b)+.

El siguiente gráfico, ¿qué expresión regular representa?. ( (a b) |a ) c*. (abc*). (ab) |ac*. (aa)+ bc*.

El siguiente gráfico, ¿qué expresión regular representa?. a+b*c. (ab)*c+. (a|b*)c. ab*c.

Un autómata es determinista cuando el número de símbolos que lo conforman es fijo. v. f.

Un autómata es no determinista cuando no se puede determinar el número de cadenas que lo conforman. v. f.

En la definición de un autómata finito determinista interviene la función de transición, esta indica cual es el siguiente símbolo que va a ser procesado por el autómata. v. f.

Un autómata finito determinista puede tener mas de un estado de aceptación. v. f.

El lenguaje del AFD es el conjunto de todas las cadenas que acepta. v. f.

El símbolo * implica que la expresión regular se debe repetir cero o más veces. v. f.

Un autómata finito no determinista reconoce entradas que se forman a partir de un alfabeto. v. f.

Si un autómata finito debe procesar la entrada “abcd”, el primer símbolo en procesar es “a”. v. f.

La expresión regular a+b+ permite reconocer la cadena “aaaaab”. v. f.

La expresión regular (a|b*) permite reconocer la cadena “aaa”. v. f.

El diagrama de transiciones es una representación gráfica de un autómata. v. f.

La tabla de transiciones permite representar las cadenas que va a reconocer el autómata. v. f.

En un autómata finito no determinista permite que de un estado puedan salir más de una misma transición a diferentes estados. v. f.

La diferencia entre un AFND y un AFD está en la función de transición, en la que en el caso de AFND devuelve un conjunto de estados y el AFD devuelve un solo estado. v. f.

Una transición vacía se refiere a un estado vacío. v. f.

Si en un programa fuente se utiliza una variable que no ha sido declarada, se trata de un error de tipo léxico. v. f.

Un alfabeto es un conjunto de símbolos finito y no vacío. v. f.

Se utiliza el símbolo Σ para representar un lenguaje. v. f.

Σ = {0,1}, representa el conjunto de los números dígitos. v. f.

Una cadena de caracteres, a veces denominada palabra, es una secuencia de símbolos seleccionados de algún alfabeto. v. f.

La cadena vacía es aquella cadena que presenta cero apariciones de símbolos. v. f.

La longitud de una cadena se mide por el número de símbolos que contiene la cadena. v. f.

Al considerar los conceptos relacionados con potencia de un alfabeto se puede decir que Σ3 = {00, 01, 10, 11}. v. f.

Un lenguaje es un conjunto (posiblemente infinito) de cadenas, donde los símbolos de todas ellas se han seleccionado de un determinado alfabeto. v. f.

Los autómatas finitos utilizan estados y transiciones entre estado en respuesta a las entradas. v. f.

Un autómata finito no determinista es aquel que solo puede estar en un único estado después de leer cualquier secuencia de entradas. v. f.

Un autómata finito determinista se define por la quíntupla de los siguientes componentes: A = (Q, Σ, δ, q0, F). v. f.

Un diagrama de transiciones es una representación tabular convencional de una función que toma dos argumentos y devuelve un valor. v. f.

En los AFD, los nodos correspondientes a los estados de aceptación, están marcados con un doble círculo. v. f.

Un lenguaje regular son aquellos que pueden describirse mediante un autómata finito. v. f.

Un lenguaje del AFD es el conjunto de todas las cadenas que acepta. v. f.

La diferencias entre los AFD y los AFN se encuentra en le tipo de función de transición. v. f.

Una función de transición, describirá lo que ocurre cuando se parte de cualquier estado y se sigue cualquier secuencia de entradas. v. f.

De las siguientes cadenas, cuál de ellas es una cadena de Σ = {a,b,…..,z}: 01101. 01ab110. bzabbd.

La longitud de la cadena |abbcdaa| es igual a: 4. 7. 5.

Una expresión regular: Define un lenguaje. Resume una cadena. Amplia una sentencia.

De los siguientes operadores, ¿cuál no es un operador de las expresiones regulares?. *. +. . 2 (cuadrado).

La concatenación de los lenguajes L y M, se designan como: L U M. LM. LM*.

Sea L y M lenguajes, (LM)N = L(MN), expresa la propiedad: Conmutatividad para la unión. Asociativa para la concatenación. Asociativa para la unión.

¿Cuál de las siguientes expresiones regulares representa el lenguaje formado por todas las cadena {a, b}, tales que toda a este precedida por una b?. b(ba)*. ab*(ba). (ba)ab*.

Si L = {001, 10, 111} y M = {ε, 001}, entonces L U M = {ε, 10, 001, 111}. V. F.

Si L = {0, 11}, entonces L* constará de aquellas cadenas de 0s y 1s tales que los 1s aparezcan por parejas, como por ejemplo 011, 11110 y vacío (ε). V. F.

La construcción de una expresión regular para definir el lenguaje de cualquier AFD, consiste en construir expresiones que describan conjuntos de cadenas que etiqueten ciertos caminos del diagrama de transiciones de una AFD. V. F.

La asociatividad es la propiedad de un operador que establece que se puede cambiar el orden de sus operandos y obtener el mismo resultado en le álgebra de expresiones. V. F.

La precedencia más alta de los operadores en las expresiones regulares, la tiene el operador de concatenación o punto. V. F.

La clausura respecto de ε (Epsilon=vacío) de un estado, se realiza siguiendo todas las transiciones salientes de un estado q que estén etiquetadas con ε y todos las transiciones que estén relacionadas con ε de dicho estado. V. F.

Ø + L = L + Ø = L, establece que Ø es el elemento identidad para la unión. V. F.

La propiedad de clausura permite construir reconocedores para lenguajes que se han construido a partir de otros lenguajes mediante ciertas operaciones. V. F.

La diferencia de L y M, es el conjunto de cadenas que pertenecen al lenguaje L pero no al lenguaje M. V. F.

Escoja la cadena que es la reflexión de “asd”. asdasd. dsadsa. asd. dsa.

Dado el homomorfismo f, f(0)=a y f(1)=vacio, cuál de las cadenas se genera al aplicar el homorfismo sobre la cadena “0101”. ab. aa. bb.

La reflexión de un lenguaje regular es regular. V. F.

Los lenguajes regulares son cerrados para las tres operaciones booleanas: unión, intersección y complementación. V. F.

El homomorfismo se refiere al reemplazamiento de un símbolo por una cadena. V. F.

La intersección de dos lenguajes regulares es regular. V. F.

La cerradura vacía de s equivale al conjunto de todos los estados que se pueden alcanzar desde el estado s utilizando únicamente un símbolo de entrada. V. F.

La cerradura vacía de T equivale a la cerradura vacía de s para cada estado s de T. V. F.

El lenguaje es: Un conjunto de símbolos del alfabeto. Un conjunto de cadenas del alfabeto. Un conjunto de palabras formadas a partir de diferentes alfabetos. Un conjunto de palabras formadas a partir de un alfabeto.

El alfabeto es: Un conjunto de palabras basadas sobre un alfabeto. Un conjunto de símbolos. Un conjunto de elementos resultantes de la cerradura vacía del alfabeto. Un conjunto de símbolos de un lenguaje.

Las palabras se forman: Concatenando cadenas. Concatenando símbolos del lenguaje. Concatenando símbolos del alfabeto.

Cual de las siguientes expresiones regulares puede generar la cadena 0101010. (10)0+. (101) +. 0(10) +. (010)+.

El autómata finito determinista. Tiene vacíos. Puede estar en más de un estado a la vez. No tiene vacíos y no puede estar en más de un estado a la vez. Tiene vacíos y no puede estar en más de un estado a la vez.

¿Cuál de los siguientes elementos no son parte de un autómata finito determinista?. El conjunto de estados finales. Símbolos de entrada. Los símbolos que etiquetan el estado de la transición. La función de transición.

Una expresión regular es: Una forma de expresar cadenas. Una forma de resumir un lenguaje. Generador de cadenas vacías y no vacías.

En la siguiente expresión regular ((a + b)*)*, ¿cuál es la operación que se ejecuta primero?. El +. El primer *. El segundo *.

Dados los lenguajes L=(1,2) y M=(2,3,4). La concatenación es: C=(2). C=(2,3,4). C=(1,2,3,4).

Dadas las cadenas X=abc e Y=cde. ¿Cuál de las siguientes cadenas representa la concatenación de X e Y?. ac, ad, ae, bc, bd, be, cc, cd, ce. abccde. abc, cde. Ninguna de las anteriores.

¿Cuál de las siguientes expresiones regulares permite generar todas las cadenas de letras minúsculas que empiezan y terminan con a?. l=letra. l(a|b|..|z)+l. a(l)+. a(l)+a. l(a)+a.

El símbolo ∑ significa. Lenguaje. Alfabeto. Conjunto de estados.

La tabla de transiciones cuenta con. Filas que representan los elementos del alfabeto y columnas que representan los estados finales. Filas que representan los estados finales y columnas que representan los estados de destino. Filas que representan los símbolos del alfabeto y columnas que representan los estados de destino. Filas que representan los estados finales y columnas que representan los símbolos del alfabeto.

abcabcbb. (abc) +b. (abc) +b+. (abcabc)b. (abc)(abc).

Una transición vacía. Permite mover elementos de entrada a través de una transición. Permite cambiar de estado consumiendo un elemento del alfabeto. Permite cambiar de estado sin consumir elementos del alfabeto.

Si A es un lenguaje regular y B es un lenguaje regular. La intersección de los dos lenguajes no es regular. La unión de los lenguajes es regular. El complemento del lenguaje A no es regular.