Test: TALF Trivia Challenge


TALF Trivia ChallengeVersión en línea Test your knowledge about TALF with these fun quiz questions! por 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

Test

Descarga la versión para jugar en papel

Creada por

Top 10 resultados

Top juegos

Test

Cultura general española

Test

Brawl stars preguntas

Test

Verbos irregulares en Inglés

Test

cuanto sabes de Futbol

Test

Tipos de sintagmas (II)