1Puntos:1

Seleccioneunarespuesta.

a.Elalfabetodelacintayelalfabetodeentradapuedeserelmismo(losmismossmbolos)

b.Enlacintanopuedenquedarcadenascompuestasporelalfabetodeentrada

c.ParaqueseareconocidaunacadenaenlaMTlacintadebequedarvaca(soloconsmbolosblanco)

d.Elalfabetodelacintadebeserdiferentealalfabetodeentrada

Conrespectoalalfabeto(smbolos)delacintaenunamquinadeTuring(MT)yelalfabeto(smbolos)deentrada,identificaqueapreciacionessonvlidas:

2Puntos:1

Seleccioneunarespuesta.

a.Todaslasmquinas(A,B,C)secomportancomoMTycomotransductores

b.Lasmquinas"A"y"C"sonAFND

c.Paraquelamquina"C"secomportecomotransductor,necesitaqueelestadoq0tambinseafinal.

d.LamquinaBdemuestraqueunaMTsepuedecomportarcomotransductor

Dadaslassiguientestresmquinas(A,B,C)ydeterminequcaractersticassonvlidasensuanlisis:

3Puntos:1

Seleccionealmenosunarespuesta.

a.Losparescodificadossoncuatro(4).esdecir8bits

b.Losparescodificadossonocho(8).esdecir16bits

c.Elnmerodeestadoses:2(potenciak(n1))Dnde:K=eselnmerodebitsdelacadenaaevaluar(antesdesercodificada).m=lamemoriadelcodificador(esrestringida)n=esunasalidacodificada(nmerodebits).SiK=1n=3.Eltotaldeestadosescuatro.

d.Elnmerodeestadoses:2(potenciak(m1))Dnde:K=lasecuenciaencantidaddebitsquevanaentraralcodificador.m=lamemoriadelcodificador(esrestringida)n=esunasalidacodificada(nmerodebits).

Seleccionedosopciones:Unaqueidentifique:ElnmerodeestadosposiblesparaundiagramadeestadosOtraqueidentifique:Losparescodificadosenuncodificadorconvolucionalderatio1/2

4Puntos:1

Seleccionealmenosunarespuesta.

a.LasdosmquinasreconocenelmismolenguajeL=a*sobre={a}

b.LaMT(A)noaceptacadenasvacas

c.LaMT(A),paracadacadenavlidaquelee,alfinaldelclculodesocupalacinta

d.LaMT(A)paracadacadenavlidaquelee,alfinaldelclculodejalacintaconlossmbolosXXX

1.IdentifiquequecaractersticasaplicanalanlisisquehagadelassiguientesdosMquinasdeturing(MT).

5Puntos:1

Seleccioneunarespuesta.

a.ElproblemadeparadasoloaplicaaMquinasdeTuringnodeterministas.LasDeterministassolucionanesteproblema

b.Seproduceunaterminacinanormal(esdecir,lacabezalectorasedesplazaalaizquierdadelaprimeraceldadelacinta)

c.Lamquinanosedetienenunca

d.Lamquinaabandonalosclculospornoencontrarningunatransicinaplicable

SeleccioneculdelassiguientessituacionesnoesposiblecuandounamquinadeTuringdeterministaexaminaunacadena:

Quiz2

AUTOMATASYLENGUAJESFORMALES301405A_220 Perfil Salir

Tiemporestante

0:55:09

campus13_20151 301405A_220 Cuestionarios Quiz2 Intento1

6Puntos:1

Seleccionealmenosunarespuesta.

a.Sololamquina"B"secomportacomounAutmatayaquecontieneunestadodeaceptacnHaltylasotrasdosmquinasno

b.Lamauina"A"esunmquinadeMoore

c.Todaslasquinassecomportancomotransductores

d.Lasmquinas"A"y"C"sonrepresentacionesdeunamuinadeMealy

1.Dadaslassiguientestresmquinas(A,B,C)ydeterminequcaractersticassonvlidasensuanlisis.

7Puntos:1

Seleccioneunarespuesta.

a.Simulacualquierlenguajegeneradoporunagramticadada.

b.EsunamquinaqueescapazdesimularcualquierotramquinadeTuring.(MT)

c.LaMUTsediseparasimularalgoritmosquesolucionanproblemasinfinitos

d.Esunamquinaquequedestinadasoloparareconocerundeterminadolenguaje

LacaractersticaporlaquesedefinioformulunaMaquinaUniversaldeTuring(MUT)fue:

8Puntos:1

Seleccioneunarespuesta.

a.SilaprimeraletranoesunaalaMTcaeenuncicloinfinitoleyendoyescribiendoa

b.Lamquinaaceptapalabrasqueempiezanconbseguidasde"a"

c.Silaprimeraletradelapalabradeentradaesuna"a",siemprereconocermasdeuna"b"seguidaysedetendr.

d.Silaprimeraletranoesunaa,laMTcaeenuncicloinfinitoleyendoyescribiendob

DadalasiguienteMquinadeTuring(MT),determinequeafirmacionessonvlidasparasuanlisis:

9Puntos:1

Seleccioneunarespuesta.

a.(01110001)

b.(10001110)

c.(01100101)

d.(10011010)

13Dadoelsiguientediagramaderbol(teoradelacodificacin)identifiqueculfueeldatodeentrada.

10Puntos:1

1.LasiguienteMquinadeTuring(MT)reconoceellenguajeL={aibici:i0}sobre={a,b,c}.Identifiquequeotracaractersticavlidaespropiadeella:

Seleccioneunarespuesta.

a.LacintasiempreterminaconXXYYZZparacualquiercadenavlida

b.Lacintasiemprequedavaca

c.Cuandoreconoce(aaabbbccc)lacintaquedaconXXXYYYZZZ

d.CuandoreconoceunacadenavlidalacintasiemprequedaconZYZ

11Puntos:1

Seleccioneunarespuesta.

a.LadistanciadeHammingenelestado(10)cuandoinicialalecturadeldatoesde2

b.LadistanciadeHammingenelestado(10)cuandoinicialalecturadeldatoesde3

c.LadistanciadeHammingenelestado(11)esde2

d.LadistanciadeHammingenelestado(01)cuandoinicialalecturadeldatoesde3

1.DadalasiguientemalladeViterbiparaefectosdedecodificacin,identifiquequeanlisissonvlidoparaesarutayadecodificadaycorrecta:

12Puntos:1

Seleccioneunarespuesta.

a.EnunaMTrepresentalacadenavaca

b.DeterminacuandounacadenaesreconocidaparaquesedetengalaMquinadeTuring.(MT)

c.Hacepartedelalfabetodelacintayestalaizquierdayderechadelacinta

d.Estnsituadosalextremoizquierdodelacintayhacepartedelalfabetodeentrada

DentrodeloscomponentesdeunamquinadeTuring(MT),estelsmboloblancoB.Elcomportamientodeestesmboloes:

13Puntos:1

Seleccioneunarespuesta.

a.Posicindeestado(01)conentradadedato1.Cambiodeestado10consalidadedatocodificado{00}

b.Posicindeestado(11)conentradadedato0.Cambiodeestado11consalidadedatocodificado{01}

c.Posicindeestado(01)conentradadedato0.Cambiodeestado10consalidadedatocodificado{11}

d.Posicindeestado(00)conentradadedato1.Cambiodeestado00consalidadedatocodificado{01}

EldiagramadeViterbi,dentrodesusinteraccionesovalidacindedatosdefineelcambiodeestadosdeacuerdoalosdatosdeentrada.Identifiqueeldatodeentradacorrectoysucambiodeestadoconeldatodesalidacodificadocorrectamente.

14Puntos:1

Seleccionealmenosunarespuesta.

a.SiUnaMTpuedesolucionarunproblemaunaMquinarealtambinsolucionaelmismoproblema

b.LasmquinasrealestienemayorpoderdecomputacinqueunaMquinadeTuring(MT)

c.UnaMUTesunaabstracciondeunamquinareal.Secomportandeigualforma.

d.TodafuncincomputabletieneunalgoritmodecidibleprounaMT

DentrodelastesisqueplasmaronChurchyTuring,estunadelasmsaplicadasydemostradashoyenda,enfocadaalfuncionamientodelasmquinasreales(comutadoras).Estasson:

15Puntos:1

Seleccioneunarespuesta.

a.Reconoce{apotencia"n"bpotencia"n":n1}

b.Reconoce{apotencia"n"bpotencia"m":n1m2}

c.Reconoce{apotencia"n"bpotencia"m":n2m1}

d.Reconoce{apotencia"n"bpotencia"n":n1}

1.EvalesiasiguienteMquinadeTuring(MT)eidentifiquequecaractersticaespropiadeella:

ParaM=(K,,,q0,F,B,)dondeK={q0,q1,q2,q3,q4},F=q4,={a,b},={M,N,}

Guardarsinenviar Enviartodoyterminar

UstedsehaautentificadocomoWILLIAMANDRESROSERO(Salir)

301405A_220