Teoría de Autómatas primer bimestre

En el análisis léxico se busca reconocer cadena. 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 del alfabeto 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 cuál es el siguiente símbolo que va a ser procesado por el autómata. V. F.

Un autómata finito determinista puede tener más 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.

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.

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.