Automatas UOC

Examen 2010/11-2

Assignatura Codi Data Hora inici

Teoria d’autòmats i llenguatges formals II 05.016 11/06/2011 18:30

Pàgina 1 de 6

Ì05.016Â11Â06Â11ÂEXPÎ

05.016 11 06 11 EX

Enganxeu en aquest espai una etiqueta identificativa

amb el vostre codi personal

Examen

Fitxa tècnica de l'examen

• Comprova que el codi i el nom de l’assignatura corresponen a l’assignatura en la qual estàs

matriculat.

• Només has d’enganxar una etiqueta d’estudiant a l’espai corresponent d’aquest full.

• No es poden adjuntar fulls addicionals.

• No es pot realitzar la prova en llapis ni en retolador gruixut.

• Temps total: 2 h.

• En cas que els estudiants puguin consultar algun material durant l’examen, quin o quins

materials poden consultar?

Es poden consultar com a màxim dos fulls mida A4 per les dues cares amb apunts.

• Valor de cada pregunta: Totes les preguntes tenen el mateix pes (12,5% de la nota global cada una)

• En cas que hi hagi preguntes tipus test: Descompten les respostes errònies? NO Quant?

• Indicacions específiques per a la realització d’aquest examen:

Enunciats

Trieu l’opció correcta i justifiqueu la resposta dins el requadre corresponent.

Pregunta 1

La funció f(x) = 1 si Dom(ϕx) és finit, 0 altrament és:

a) Calculable total.

b) Ni total ni calculable.

c) Calculable no total.

d) No calculable però total.

Espai

grapa

Examen 2010/11-2

Assignatura Codi Data Hora inici

Teoria d’autòmats i llenguatges formals II 05.016 11/06/2011 18:30

Pàgina 2 de 6

És total, ja que està definida per a tots els valors, però no és calculable, ja que caldria saber, donada una

funció, si no té el domini finit, és a dir, si no està definida per a algun valor, cosa que no podem calcular, ja

que si poguéssim calcular quan una funció no acaba per a una entrada determinada, llavors K seria REC.

Per tant, la resposta correcta és la d).

Pregunta 2

Si A és un conjunt REC, B és un conjunt ER i C és un conjunt no-ER, digues quina de les següents

afirmacions és certa:

a) A intersecció B pot ser no-ER.

b) A intersecció C és sempre no-ER.

c) B intersecció C pot ser ER.

d) A unió C pot ser finit.

L’opció a) és incorrecta perquè ER és tancat per la intersecció, i un conjunt REC també és ER.

L’opció b) no és correcta: el conjunt buit és REC i la seva intersecció amb qualsevol conjunt no-ER serà el

conjunt buit i per tant REC.

L’opció correcta és la c): B intersecció C pot ser ER. Per exemple, K (un conjunt ER) intersecció no-K (un

conjunt no-ER) és el conjunt buit, que és REC i per tant ER.

L'opció d) no pot ser correcta, ja que C és infinit per definició (altrament seria REC) i, per tant, la unió no

pot ser finita.

Pregunta 3

Digues quina afirmació és certa:

a) No hi ha cap programa que enumeri un subconjunt finit dels elements que pertanyen a un conjunt

no-ER.

b) La funció característica d’un conjunt no-ER no és calculable.

c) Algun conjunt no-ER és finit.

d) Els conjunts ER no poden ser finits.

Examen 2010/11-2

Assignatura Codi Data Hora inici

Teoria d’autòmats i llenguatges formals II 05.016 11/06/2011 18:30

Pàgina 3 de 6

L’opció a) és falsa: qualsevol subconjunt finit d’un conjunt no-ER és enumerable per una màquina de

Turing (per això els conjunts finits són sempre REC).

L’opció correcta és la b) per la definició de conjunt no-ER.

L’opció c) tampoc és correcta, tots els conjunts finits són REC.

L’opció d) és falsa, ja que els REC, que poden ser finits, també són ER.

Pregunta 4

Sabem que 3-SAT és un problema NP-complet i volem demostrar que el problema S és NP-complet. Quina

de les següents afirmacions és certa?

a) Podem assegurar que S és NP-complet si S <= 3-SAT.

b) Podem assegurar que

...