Quiz: TALF Trivia Challenge


TALF Trivia ChallengeOnline version Test your knowledge about TALF with these fun quiz questions! by Noa Mesejo 1 INDICA LAS VERDADERAS: Escoge una o varias respuestas a Dos lenguajes regulares son equivalentes si los estados iniciales de sus correspondientes autómatas finitos deterministas son equivalentes b Si S y R son dos expresiones regulares, se cumple que R(RS+S)S = RR(RRS) c Dada una gramática G que genera el lenguaje L, si una cadena de L se puede obtener con dos derivaciones diferentes, entonces G es ambigua. d Si L es un lenguaje recursivamente enumerable y MT una máquina de Turing que lo acepta, para cualquier cadena w que no pertenezca a L, la máquina MT siempre se parará, pero no en un estado final 2 INDICA LAS VERDADERAS: a Para simular una MT multicinta con una MT estándar es necesario utilizar N pistas, siendo N el número de cintas de la MT multicinta b En una MT bidimensional, la cabeza de lectura/escritura se puede mover en cuatro direcciones c Una MT Universal solo tiene 3 cintas d Atendiendo a la complejidad computacional, una MT multicinta y una MT estándar son equivalentes 3 INDICA LAS VERDADERAS: Escoge una o varias respuestas a Un Autómata Linealmente Acotado es una MT no determinista con su cinta limitada por ambos extremos, siendo el tamaño de la cinta fijo b Una MT universal tiene tres cintas: una que define la MT a simular, otra el contenido de su cinta y otro el estado de la misma c Una MT con una cinta semiinfinita se simula mediante una MT estándar con dos pistas d Los problemas de tipo NP son aceptados por una MT no determinista en tiempo polinómico 4 INDICA LAS VERDADERAS (RESPECTO A LOS AF) Escoge una o varias respuestas a Pueden ser deterministas y no deterministas, pero los dos tipos son equivalentes b La función de transición en el caso de ser determinista, indica para cada entrada cual es el estado siguiente o destino para cada estado del autómata c Si es no determinista tendrá transiciones no definidas entre estados d Si un autómata es equivalente al otro, los dos tendrán el mismo número de estados en su representación mínima e Si un autómata es determinista, tendrá una expresión regular asociada, pero no si es no determinista 5 INDICA LAS VERDADERAS (RESPECTO A LOS AP) Escoge una o varias respuestas a Un AP es un AFN con transiciones asociadas a la cadena vacía y con una pila en al que se puede almacenar una cadena de símbolos b Un AP puede almacenar una cantidad infinita de información por tener un número ilimitado de posibles estados c En un AP por vaciado de pila, una secuencia será aceptada si empezando en el estado inicial se termina con la pila con un solo símbolo, el Z0 o símbolo inicial de pila d Podemos convertir un AP por estado final en un AP por vaciado de pila y viceversa siempre que tengan el mismo número de estados e Los AP deterministas reconocen lenguajes a medio camino entre los lenguajes regulares y los independientes del contexto 6 INDICA LAS VERDADERAS (RESPECTO A LAS MT): Escoge una o varias respuestas a La MT termina su operación después de leer todo el conjunto de símbolos de la cinta b Se detiene en el caso de que no esté definida la transición para la combinación (estado interno, símbolo leído en la cinta) c Se detiene cuando llega a un estado final d Una secuencia de símbolos será reconocida por una MT siempre que esta se detenga, independientemente del estado al que se llegue y del contenido de la cinta e Una MT no determinista puede aceptar ciertos lenguajes que no pueden ser aceptados por una MT determinista f Un lenguaje recursivamente enumerable se asocia a una MT, pero esta podría no detenerse nunca en el caso de analizar secuencias que no son del lenguaje. 7 INDICA LAS VERDADERAS Escoge una o varias respuestas a Si L es un lenguaje recursivo y M una máquina de Turing que la acepta, para una cadena w que no pertenezca a L, la máquina M se parará en un estado no final o entrará en un bucle infinito b Desde el punto de vista de la decibilidad, una MT estándar y una MT multicinta son equivalentes c Un lenguaje pertenece a la clase de complejidad P si existe una MT no determinista que lo acepte en tiempo polinómico d Un lenguaje L pertenece a la clase de complejidad NP-completa si L ∈ NP y es reducible en tiempo polinómico. 8 INDICA LAS VERDADERAS Escoge una o varias respuestas a Una gramática independiente del contexto no es ambigua si cada XXXXXXXXX lenguaje tiene un único árbol de derivación b En las gramáticas en forma normal de Greibach, un analizador sintático XXXXX a la profundidad N, siendo N el tamaño de la palabra c En las gramáticas en forma normal de Chomsky, un analizador sintático XXXXXXX a la profundidad N, siendo N el tamaño de la palabra analizada d Dados dos números en un alfabeto unario, el lenguaje que da dXXXXXXXX izquierda es mayor que el de la derecha, es un lenguaje recursivo 9 INDICA LAS VERDADERAS: (parcial diciembre 2017) Escoge una o varias respuestas a Si L es un lenguaje recursivamente enumerable (LRE) y M una MT que lo acepta, para cualquier cadena que no pertenezca a L la máquina M siempre se parará en un estado no final b Un problema es decidible si existe una MT que da la respuesta correcta para cada argumento del dominio c Desde el punto de vista de la complejidad, una MT estándar y una MT multicinta son equivalentes d Un lenguaje pertenece a la clase de complejidad P si existe una MT determinista que lo acepta en tiempo polinómico 10 INDICA LAS VERDADERAS: Escoge una o varias respuestas a Toda ER puede convertirse en un AF equivalente b Siempre se puede escribir una expresión regular para cualquier lenguaje libre de contexto c Todos los lenguajes reconocidos por autómatas de estados finitos son lenguajes regulares d Las ER no pueden representar lenguajes con un número infinito de palabras 11 INDICA LAS VERDADERAS (AFN): a Los AFN pueden tener pueden tener múltiples estados iniciales b Los AFN son más potentes que los deterministas en términos de reconocimiento de lenguajes c Los AFN pueden tener transiciones con la cadena vacía d Cada AFN se puede convertir en un determinista equivalente si el lenguaje regular asociado a ambos es finito 12 INDICA LAS VERDADERAS (LR): a Todos los LR son también libres de contexto b Hay lenguajes libres de contexto que son regulares c Los lenguajes regulares no pueden ser infinitos d Los lenguajes regulares no permiten definiciones recursivas 13 INDICA LAS VERDADERAS (AP): Escoge una o varias respuestas a No pueden tener transiciones en las que solo leen de la pila sin consumir entrada b Pueden determinar el final de la entrada dejando símbolos sin leer en la pila c Pueden cambiar a un estado final sin necesidad de vaciar la pila d Son equivalentes a los autómatas finitos no deterministas en términos de reconocimiento de lenguajes 14 INDICA LAS VERDADERAS (LIC): Escoge una o varias respuestas a Todos los lenguajes regulares de tamaño infinito son también independientes de contexto b Todos los lenguajes independientes del contexto de tamaño finito son regulares c Los lenguajes independientes de contexto no pueden ser infinitos d Los lenguajes independientes de contexto pueden describir lenguajes con dependencias a larga distancia, como son las cadenas de paréntesis bien formadas, como “(())”.... 15 INDICA LAS VERDADERAS (LENGUAJES DEPENDIENTES DEL CONTEXTO): Escoge una o varias respuestas a Son reconocidos por autómatas de pila b Son estrictamente más poderosos que los LIC c Son cerrados bajo la operación de intersección d Pueden ser reconocidos por MT linealmente acotadas 16 INDICA LAS VERDADERAS (GSR): Escoge una o varias respuestas a Pueden generar lenguajes que requieren un número específico de repeticiones de ciertos símbolos b Son menos poderosas que las GIC c Pueden ser usadas para describir lenguajes de programación d Son equivalentes en poder a las MT 17 INDICA LAS VERDADERAS (MT): a Una MT solo puede tener un número finito de estados b Pueden resolver cualquier problema computable c Las MTU son equivalentes a los computadores modernos en términos de tipos de problemas que pueden resolver, pero no las MT estándar d Siempre terminan su ejecución, aunque puede ser tras un número teóricamente infinito de pasos 18 CUALES SON VERDADERAS (MT ESTÁNDAR) a Los símbolos de la cinta son los del alfabeto de símbolos de entrada (secuencias a procesar), más el símbolo blanco. b La lectura de cada posición o celda de la cinta supone la escritura en ella c La función de transición para los estados finales supone continuar en ellos independientemente del símbolo que se lea en la cinta d Su tamaño depende del tamaño del problema a resolver 19 INDICA LAS VERDADERAS (En el contexto de la computabilidad, las MT…): a Pueden decidir todos los problemas de decisión b Son un modelo teórico que equivale al concepto de algoritmo c Son capaces de simular la ejecución de cualquier algoritmo asociado a una función computable, salvo algunos problemas NP-completos d Solo son superadas en su capacidad de resolución teórica de problemas por los computadores cuánticos 20 INDICA LAS VERDADERAS (variantes MT): a Las MT estándar son estrictamente más poderosas que las MT con cintas limitadas en tamaño, aunque usen varias b Las MT con cinta limitada reconocen lenguajes recursivos, pero no los recursivamente enumerables c Las MT no deterministas pueden simplificar la representación de soluciones a ciertos problemas frente a las deterministas d Las MTU son capaces de simular cualquier otra MT y viceversa 21 INDICA LAS VERDADERAS (MT): a La MT termina su operación después de leer todo el conjunto de símbolos de la cinta b Se detiene en el caso de que no esté definida la transición para la combinación (estado, símbolo) c Se detiene cuando llega a un estado final d Un LRE se asocia a una MT, pero esta podría no detenerse nunca en el caso de analizar secuencias que no son del lenguaje 22 INDICA SI SON VERDADERAS Escoge una o varias respuestas a El lenguaje L = {x \| x ∈ (a+b), y N(a), N(b) son números primos de dos cifras} es regular b El lenguaje L = {a^i b^i c^i \| i es un número de dos cifras} es regular c El lenguaje L = {a^i b^j c^k \| i = k, y j es par si i es par, e impar en caso contrario} es independiente de contexto d Un autómata linealmente acotado es una MT no determinista con la cinta limitada por ambos extremos, y de [...] tamaño de la cinta es fijo independientemente del tamaño de la cadena de entrada e Una MT universal consta de tres cintas que contienen la definición de la MT a simular, el  contenido de la cinta de la MT y el estado de la MT a simular f Una MT con cinta semi-infinita se simula mediante una MT estándar con dos pistas 23 INDICA SI SON VERDADERAS Escoge una o varias respuestas a Los problemas de tipo NP son aceptados por una MT no determinista en tiempo polinómico b Si L es un lenguaje recursivamente enumerable (LRE) y M una máquina de Turing (MT) que lo acepta, para cualquier cadena w que no pertenezca a L la máquina M siempre se parará en un estado no final c Un problema es decidible si existe una MT que da la respuesta correcta para cada argumento del dominio d Desde el punto de vista de la complejidad, una MT estándar y una MT muticinta son equivalentes e Un lenguaje pertenece a la clase de complejidad P si existe una MT determinista que lo acepta en tiempo polimórfico f Un lenguaje pertenece a NP si no existe ninguna MT no determinista que lo acepte en tiempo humano 24 Aplicando el Lema del Bombeo para lenguajes regulares al lenguaje  L = {x \| x E (a+b), N(a) es múltiplo de 2 y N(b) es múltiplo de 3}: a El lenguaje es regular (se reconoce con un AF) b La descomposición x = ε, y = aa, z=a2n-2b3n verifica el lema de bombeo c La descomposición x = ε, y = a^(2n), z = b^(3n) verifica el lema de bombeo 25 Verdaderas? Escoge una o varias respuestas a Autómatas son equivalentes si sus estados iniciales son equivalentes b Máquinas de turing equivalentes por complejidad c AFN y AFD son equivalentes d MT parará en estado no final si lee a w que no pertenece a un lenguaje que acepta la MT e Máquina de turing multicinta conformado por n cintas de máquinas estándar f Máquina universal de turing tiene solo 3 cintas 26 Verdaderas? Escoge una o varias respuestas a Máquina universal de turing tiene 3 cintas llamadas: … (tal cual la teoría) b Para pasar de autómata de pila de final estado a vaciado de pila se puede hacer solo si tienen mismo número de estados c Los AP deterministas aceptan un conjunto de lenguajes a medio camino entre los lenguajes regulares y las GIC. d La máquina de turing semiinfinita se simula con una máquina estándar con dos pistas e La máquina de turing no determinista permite aceptar más lenguajes que la estándar f Un AFD tiene expresión regular asociada y un AFN no 27 Verdaderas? a Habían dos expresiones regulares y preguntaba si eran equivalentes R(R+S)S = RR(RRS) b Las máquinas de turing bidimensionales se mueven en 4 direcciones c Una gramática es ambigua si tiene varias derivaciones para una palabra w d Una autómata de pila es un AFN con transiciones E y con pila donde almacenar cadenas

1

INDICA LAS VERDADERAS:

Escoge una o varias respuestas

a

Dos lenguajes regulares son equivalentes si los estados iniciales de sus correspondientes autómatas finitos deterministas son equivalentes

b

Si S y R son dos expresiones regulares, se cumple que R(RS+S)*S = RR*(RR*S)*

c

Dada una gramática G que genera el lenguaje L, si una cadena de L se puede obtener con dos derivaciones diferentes, entonces G es ambigua.

d

Si L es un lenguaje recursivamente enumerable y MT una máquina de Turing que lo acepta, para cualquier cadena w que no pertenezca a L, la máquina MT siempre se parará, pero no en un estado final

2

INDICA LAS VERDADERAS:

a

Para simular una MT multicinta con una MT estándar es necesario utilizar N pistas, siendo N el número de cintas de la MT multicinta

b

En una MT bidimensional, la cabeza de lectura/escritura se puede mover en cuatro direcciones

c

Una MT Universal solo tiene 3 cintas

d

Atendiendo a la complejidad computacional, una MT multicinta y una MT estándar son equivalentes

3

INDICA LAS VERDADERAS:

Escoge una o varias respuestas

a

Un Autómata Linealmente Acotado es una MT no determinista con su cinta limitada por ambos extremos, siendo el tamaño de la cinta fijo

b

Una MT universal tiene tres cintas: una que define la MT a simular, otra el contenido de su cinta y otro el estado de la misma

c

Una MT con una cinta semiinfinita se simula mediante una MT estándar con dos pistas

d

Los problemas de tipo NP son aceptados por una MT no determinista en tiempo polinómico

4

INDICA LAS VERDADERAS (RESPECTO A LOS AF)

Escoge una o varias respuestas

a

Pueden ser deterministas y no deterministas, pero los dos tipos son equivalentes

b

La función de transición en el caso de ser determinista, indica para cada entrada cual es el estado siguiente o destino para cada estado del autómata

c

Si es no determinista tendrá transiciones no definidas entre estados

d

Si un autómata es equivalente al otro, los dos tendrán el mismo número de estados en su representación mínima

e

Si un autómata es determinista, tendrá una expresión regular asociada, pero no si es no determinista

5

INDICA LAS VERDADERAS (RESPECTO A LOS AP)

Escoge una o varias respuestas

a

Un AP es un AFN con transiciones asociadas a la cadena vacía y con una pila en al que se puede almacenar una cadena de símbolos

b

Un AP puede almacenar una cantidad infinita de información por tener un número ilimitado de posibles estados

c

En un AP por vaciado de pila, una secuencia será aceptada si empezando en el estado inicial se termina con la pila con un solo símbolo, el Z0 o símbolo inicial de pila

d

Podemos convertir un AP por estado final en un AP por vaciado de pila y viceversa siempre que tengan el mismo número de estados

e

Los AP deterministas reconocen lenguajes a medio camino entre los lenguajes regulares y los independientes del contexto

6

INDICA LAS VERDADERAS (RESPECTO A LAS MT):

Escoge una o varias respuestas

a

La MT termina su operación después de leer todo el conjunto de símbolos de la cinta

b

Se detiene en el caso de que no esté definida la transición para la combinación (estado interno, símbolo leído en la cinta)

c

Se detiene cuando llega a un estado final

d

Una secuencia de símbolos será reconocida por una MT siempre que esta se detenga, independientemente del estado al que se llegue y del contenido de la cinta

e

Una MT no determinista puede aceptar ciertos lenguajes que no pueden ser aceptados por una MT determinista

f

Un lenguaje recursivamente enumerable se asocia a una MT, pero esta podría no detenerse nunca en el caso de analizar secuencias que no son del lenguaje.

7

INDICA LAS VERDADERAS

Escoge una o varias respuestas

a

Si L es un lenguaje recursivo y M una máquina de Turing que la acepta, para una cadena w que no pertenezca a L, la máquina M se parará en un estado no final o entrará en un bucle infinito

b

Desde el punto de vista de la decibilidad, una MT estándar y una MT multicinta son equivalentes

c

Un lenguaje pertenece a la clase de complejidad P si existe una MT no determinista que lo acepte en tiempo polinómico

d

Un lenguaje L pertenece a la clase de complejidad NP-completa si L ∈ NP y es reducible en tiempo polinómico.

8

INDICA LAS VERDADERAS

Escoge una o varias respuestas

a

Una gramática independiente del contexto no es ambigua si cada XXXXXXXXX lenguaje tiene un único árbol de derivación

b

En las gramáticas en forma normal de Greibach, un analizador sintático XXXXX a la profundidad N, siendo N el tamaño de la palabra

c

En las gramáticas en forma normal de Chomsky, un analizador sintático XXXXXXX a la profundidad N, siendo N el tamaño de la palabra analizada

d

Dados dos números en un alfabeto unario, el lenguaje que da dXXXXXXXX izquierda es mayor que el de la derecha, es un lenguaje recursivo

9

INDICA LAS VERDADERAS: (parcial diciembre 2017)

Escoge una o varias respuestas

a

Si L es un lenguaje recursivamente enumerable (LRE) y M una MT que lo acepta, para cualquier cadena que no pertenezca a L la máquina M siempre se parará en un estado no final

b

Un problema es decidible si existe una MT que da la respuesta correcta para cada argumento del dominio

c

Desde el punto de vista de la complejidad, una MT estándar y una MT multicinta son equivalentes

d

Un lenguaje pertenece a la clase de complejidad P si existe una MT determinista que lo acepta en tiempo polinómico

10

INDICA LAS VERDADERAS:

Escoge una o varias respuestas

a

Toda ER puede convertirse en un AF equivalente

b

Siempre se puede escribir una expresión regular para cualquier lenguaje libre de contexto

c

Todos los lenguajes reconocidos por autómatas de estados finitos son lenguajes regulares

d

Las ER no pueden representar lenguajes con un número infinito de palabras

11

INDICA LAS VERDADERAS (AFN):

a

Los AFN pueden tener pueden tener múltiples estados iniciales

b

Los AFN son más potentes que los deterministas en términos de reconocimiento de lenguajes

c

Los AFN pueden tener transiciones con la cadena vacía

d

Cada AFN se puede convertir en un determinista equivalente si el lenguaje regular asociado a ambos es finito

12

INDICA LAS VERDADERAS (LR):

a

Todos los LR son también libres de contexto

b

Hay lenguajes libres de contexto que son regulares

c

Los lenguajes regulares no pueden ser infinitos

d

Los lenguajes regulares no permiten definiciones recursivas

13

INDICA LAS VERDADERAS (AP):

Escoge una o varias respuestas

a

No pueden tener transiciones en las que solo leen de la pila sin consumir entrada

b

Pueden determinar el final de la entrada dejando símbolos sin leer en la pila

c

Pueden cambiar a un estado final sin necesidad de vaciar la pila

d

Son equivalentes a los autómatas finitos no deterministas en términos de reconocimiento de lenguajes

14

INDICA LAS VERDADERAS (LIC):

Escoge una o varias respuestas

a

Todos los lenguajes regulares de tamaño infinito son también independientes de contexto

b

Todos los lenguajes independientes del contexto de tamaño finito son regulares

c

Los lenguajes independientes de contexto no pueden ser infinitos

d

Los lenguajes independientes de contexto pueden describir lenguajes con dependencias a larga distancia, como son las cadenas de paréntesis bien formadas, como “(())”....

15

INDICA LAS VERDADERAS (LENGUAJES DEPENDIENTES DEL CONTEXTO):

Escoge una o varias respuestas

a

Son reconocidos por autómatas de pila

b

Son estrictamente más poderosos que los LIC

c

Son cerrados bajo la operación de intersección

d

Pueden ser reconocidos por MT linealmente acotadas

16

INDICA LAS VERDADERAS (GSR):

Escoge una o varias respuestas

a

Pueden generar lenguajes que requieren un número específico de repeticiones de ciertos símbolos

b

Son menos poderosas que las GIC

c

Pueden ser usadas para describir lenguajes de programación

d

Son equivalentes en poder a las MT

17

INDICA LAS VERDADERAS (MT):

a

Una MT solo puede tener un número finito de estados

b

Pueden resolver cualquier problema computable

c

Las MTU son equivalentes a los computadores modernos en términos de tipos de problemas que pueden resolver, pero no las MT estándar

d

Siempre terminan su ejecución, aunque puede ser tras un número teóricamente infinito de pasos

18

CUALES SON VERDADERAS (MT ESTÁNDAR)

a

Los símbolos de la cinta son los del alfabeto de símbolos de entrada (secuencias a procesar), más el símbolo blanco.

b

La lectura de cada posición o celda de la cinta supone la escritura en ella

c

La función de transición para los estados finales supone continuar en ellos independientemente del símbolo que se lea en la cinta

d

Su tamaño depende del tamaño del problema a resolver

19

INDICA LAS VERDADERAS (En el contexto de la computabilidad, las MT…):

a

Pueden decidir todos los problemas de decisión

b

Son un modelo teórico que equivale al concepto de algoritmo

c

Son capaces de simular la ejecución de cualquier algoritmo asociado a una función computable, salvo algunos problemas NP-completos

d

Solo son superadas en su capacidad de resolución teórica de problemas por los computadores cuánticos

20

INDICA LAS VERDADERAS (variantes MT):

a

Las MT estándar son estrictamente más poderosas que las MT con cintas limitadas en tamaño, aunque usen varias

b

Las MT con cinta limitada reconocen lenguajes recursivos, pero no los recursivamente enumerables

c

Las MT no deterministas pueden simplificar la representación de soluciones a ciertos problemas frente a las deterministas

d

Las MTU son capaces de simular cualquier otra MT y viceversa

21

INDICA LAS VERDADERAS (MT):

a

La MT termina su operación después de leer todo el conjunto de símbolos de la cinta

b

Se detiene en el caso de que no esté definida la transición para la combinación (estado, símbolo)

c

Se detiene cuando llega a un estado final

d

Un LRE se asocia a una MT, pero esta podría no detenerse nunca en el caso de analizar secuencias que no son del lenguaje

22

INDICA SI SON VERDADERAS

Escoge una o varias respuestas

a

El lenguaje L = {x | x ∈ (a+b)*, y N(a), N(b) son números primos de dos cifras} es regular

b

El lenguaje L = {a^i b^i c^i | i es un número de dos cifras} es regular

c

El lenguaje L = {a^i b^j c^k | i = k, y j es par si i es par, e impar en caso contrario} es independiente de contexto

d

Un autómata linealmente acotado es una MT no determinista con la cinta limitada por ambos extremos, y de [...] tamaño de la cinta es fijo independientemente del tamaño de la cadena de entrada

e

Una MT universal consta de tres cintas que contienen la definición de la MT a simular, el  contenido de la cinta de la MT y el estado de la MT a simular

f

Una MT con cinta semi-infinita se simula mediante una MT estándar con dos pistas

23

INDICA SI SON VERDADERAS

Escoge una o varias respuestas

a

Los problemas de tipo NP son aceptados por una MT no determinista en tiempo polinómico

b

Si L es un lenguaje recursivamente enumerable (LRE) y M una máquina de Turing (MT) que lo acepta, para cualquier cadena w que no pertenezca a L la máquina M siempre se parará en un estado no final

c

Un problema es decidible si existe una MT que da la respuesta correcta para cada argumento del dominio

d

Desde el punto de vista de la complejidad, una MT estándar y una MT muticinta son equivalentes

e

Un lenguaje pertenece a la clase de complejidad P si existe una MT determinista que lo acepta en tiempo polimórfico

f

Un lenguaje pertenece a NP si no existe ninguna MT no determinista que lo acepte en tiempo humano

24

Aplicando el Lema del Bombeo para lenguajes regulares al lenguaje  L = {x | x E (a+b)*, N(a) es múltiplo de 2 y N(b) es múltiplo de 3}:

a

El lenguaje es regular (se reconoce con un AF)

b

La descomposición x = ε, y = aa, z=a2n-2b3n verifica el lema de bombeo

c

La descomposición x = ε, y = a^(2n), z = b^(3n) verifica el lema de bombeo

25

Verdaderas?

Escoge una o varias respuestas

a

Autómatas son equivalentes si sus estados iniciales son equivalentes

b

Máquinas de turing equivalentes por complejidad

c

AFN y AFD son equivalentes

d

MT parará en estado no final si lee a w que no pertenece a un lenguaje que acepta la MT

e

Máquina de turing multicinta conformado por n cintas de máquinas estándar

f

Máquina universal de turing tiene solo 3 cintas

26

Verdaderas?

Escoge una o varias respuestas

a

Máquina universal de turing tiene 3 cintas llamadas: … (tal cual la teoría)

b

Para pasar de autómata de pila de final estado a vaciado de pila se puede hacer solo si tienen mismo número de estados

c

Los AP deterministas aceptan un conjunto de lenguajes a medio camino entre los lenguajes regulares y las GIC.

d

La máquina de turing semiinfinita se simula con una máquina estándar con dos pistas

e

La máquina de turing no determinista permite aceptar más lenguajes que la estándar

f

Un AFD tiene expresión regular asociada y un AFN no

27

Verdaderas?

a

Habían dos expresiones regulares y preguntaba si eran equivalentes R(R+S)*S = RR*(RR*S)*

b

Las máquinas de turing bidimensionales se mueven en 4 direcciones

c

Una gramática es ambigua si tiene varias derivaciones para una palabra w

d

Una autómata de pila es un AFN con transiciones E y con pila donde almacenar cadenas

TALF Trivia Challenge

Quiz

Download the paper version to play

Created by

Top 10 results

Top Games

Quiz

Practice Quiz - Punnett Square, Variation, and Mutations

Quiz

Tissues - Practice Quiz

Quiz

Photosynthesis vs Cellular Respiration - Practice Quiz

Quiz

Spanish Alphabet Listening

Quiz

UPS 5 Seeing Habits Quiz