PREGUNTAS TIPO TEST TALF

Indica das seguintes afirmacións cales son verdadeiras (0,5 puntos):

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'S (RR'S)",

Dada unha gramática 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 nun estado non final.

Indica das seguintes afirmacións cales son verdadeiras (0,5 puntos):

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

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

Unha MT universal ten só 3 cintas.

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

Indica cales das seguintes afirmacións son verdadeiras (0,5 puntos):

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.

Unha 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.

Indica as respostas verdadeiras respecto dos Autómatas de Número de Estados Finito (0,5 puntos):

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

A función de 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 entre estados

Se un autómata é equivalente a outro os dous terán o mesmo número de estados na súa representación minima

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

Indica cales das seguintes afirmacións son verdadeiras sobre os Autómatas de Pila (AP) (0,5 puntos):

Un AP é un AFN con transicións asociadas á cadea baleira e con unha pila na que se pode almacenar unha cadea de simbolos

Un AP pode almacenar 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 con un só simblolo, o Zo ou símbolo inicial de pila

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

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

Cales das seguintes afirmacións son verdadeiras en relación a unha Máquina de Turing (MT) (0,5 puntos)?

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 estea 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

Una 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.

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.

Completa a expresión: A Linguaxe asociada a un Autómata Linealmente Acoutado M = {w ∈ Σ+ : q0[w] |- (Simbolos para copiar y pegar: ∈, Σ, Γ) (No pongais comas que se raya)

PREGUNTAS TIPO TEST TALF

More Quizzes