Test guachi de TALF
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.
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.
L = {x/x ∈ (a+b)*, sendo N(a) e N(b) números primos de XXXXXXXXXXX
Sin restricciones
Sensible
Independiente
Regular
L = {aibjck / i=k e j é par se tamén o é I, e impar no caso contrario.
Sin restricciones
Sensible
Independiente
Regular
L = {aibici / I é un número de dúas cifras}
Sin restricciones
Sensible
Independiente
Regular
L = {anbncn / n >= 1}
Sin restricciones
Sensible
Independiente
Regular
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
{"name":"Test guachi de TALF", "url":"https://www.quiz-maker.com/QPREVIEW","txt":"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.","img":"https:/images/course8.png"}