Test guachi de TALF

Generate a visually engaging illustration depicting various computational theory concepts like Turing machines, formal languages, and automata theory, in a modern and educational style.

TALF Language Theory Quiz

Póñase á proba co noso quiz sobre teoría das linguaxes e máquinas de Turing. Este cuestionario está deseñado para probar os seus coñecementos sobre linguaxes formales, autómatas, gramáticas e complexidade computacional.

Examina conceptos clave en linguagens recursivas e non recursivas.
Comprende a relación entre máquinas de Turing e gramáticas.
Descubre a clasificación das linguaxes dentro da teoría da computación.

12 Questions3 MinutesCreated by TestingTheory42

Indica cales son verdadeiras

Se L é unha linguaxe recursiva e M unha máquina de Turing que a acepta, para unha cadea w que non pertenza a L, a máquina M pararase nun estado non final ou entrará nun bucle infinito.

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

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

Unha linguaxe L pertence á clase de complexidade NP-completa se L ∈ NP e é reducible a L en tempo polinómico.

Indica cales son verdadeiras

Una gramática independente del contexto no es ambigua si cada XXXXXXXXXX linguaxe ten un único árbore de derivación.

Nas gramáticas en forma normal de Greibach, un analizador sintáctico XXXXXX á profundidade N, sendo N o tamaño da palabra.

Nas gramáticas en forma normal de Chomsky, un analizador sintáctico XXXXXX á profundidade N, sendo N o tamaño da palabra analizada.

Dados dous números nun alfabeto unario, a linguaxe que dXXXXXXXXXXX esquerda é maior que o da dereita, é unha linguaxe recursiva.

Indicar cales son verdadeiras

Dúas linguaxes regulares son equivalentes se os estados iniciais dos seus correspondentes autómatas finitos deterministas son equivalentes.

Se S e R son dúas expresións regulares, cómprese que R(RS+S)*S=RR*(RR*S)*.

Dada unha gramática G que xera a linguaxe L, se unha cadea de L pódese obter con dúas derivacións diferentes, entón G é ambigua.

Se L é unha linguaxe recursivamente enumerable e MT unha máquina de Turing que o acepta, para calquera cadea w que non pertenza a L, a máquina MT sempre se parará, pero nunca nun estado non final.

Indicar cales son verdadeiras

Para simular unha MT multicinta cunha MT estándar é necesario utilizar N pistas, sendo N o número de cintas da MT multicinta.

Nunha MT bidimensional, a cabeza de lectura/escritura pódese mover en catro direccións.

Unha MT universal ten só 3 cintas.

Atendendo á complexidade computacional, unha MT multicinta e unha MT estándar son equivalentes.

Indicar cales son verdadeiras

Un autómata linealmente acoutado é unha MT non determinista coa súa cinta limitada por ambos extremos, sendo o tamaño da cinta fixo.

Unha MT universal ten tres cintas. Unha define a MT a simular, outra o contido da súa cinta e a terceira o estado da mesma.

Una MT cunha cinta semiinfinita simúlase mediante unha MT estándar con dúas pistas.

Os problemas de tipo NP son aceptados por unha MT non determinista en tempo polinómico.

Indicar cales son verdadeiras respecto aos AF

Poden ser deterministas ou non deterministas, pero os dous tipos son equivalentes.

A función e transición no caso de ser determinista indica para cada entrada cal é o estado seguinte ou destino para cada estado do autómata.

Se é non determinista terá transicións non definidas entres estados.

Se un autómata é equivalente a outro, os dous terán o mesmo número de estados na súa representación mínima.

Se un autómata é determinista terá unha expresión regular asociada, pero non se é non determinista.

Indicar cales so verdadeiras respecto aos AP

UN AP é un AFN con transicións á cadea baleira e con unha pila na que se pode almacear unha cadea de símbolos

UN AP pode almacear unha cantidade infinita de información por ter un número ilimitado de posibles estados

Nun AP por baleirado de pila unha secuencia será aceptada se comezando no estado inicial remátase coa pila cun só símbolo, o Z0 ou símbolo inicial

Podemos convertir un AP por baleirado de pila e viceversa sempre que teñan o mesmo número de estados

OS AP deterministas recoñecen linguaxex a medio camiño entre as linguaxes regulares e as independentes de contexto

Indicar cales so verdadeiras respecto a MT

A MT remata a súa operación despois de ler todo o conxunto de símbolos da cinta

Detense no caso de que non esté definida a transición para a combinación (estado interno, símbolo lido na cinta)

Detense cando chega a un estado final

UNha secuencia de símbolos será recoñecida por unha MT sempre que esta se deteña, independentemente do estado ao que se chegue e do contido da cinta

Unha MT non determinista pode aceptar certas linguaxes que non poden ser aceptadas por unha MT determinista

Unha linguaxe recursivamente enumerable asóciase a unha MT, pero esta podería non deterse nunca no caso de analizar secuencias que non son da linguaxe

Test guachi de TALF

TALF Language Theory Quiz

More Quizzes