TEORIA DAUTÒMATS
I LLENGUATGES FORMALS
Educació. Materials 75
Francesc J. Ferri
TEORIA DAUTOMATSI LLENGUATGES FORMALS
UNIVERSITAT DE VALÈNCIA
2004
Collecció: Educació. Materials
Director de la collecció: Guillermo Quintas Alonso
Aquesta publicació no pot ser reproduïda, ni totalment ni parcialment, ni enregistrada en, o transmesa per, un sistema de recuperació dinformació, en cap forma ni per cap mitjà, sia fotomecànic, fotoquímic, electrònic, per fotocòpia o per qualsevol altre, sense el permís previ de leditorial.
© Lautor, 2004
© Daquesta edició: Universitat de València, 2004
Coberta:
Disseny: Pere Fuster (Borràs i Talens Assessors SL)
Tractament gràfic: Celso Hernandez de la Figuera
Correcció: Pau Viciano
Edició digital
Índex
PRÒLEG
SÍMBOLS UTILITZATS
Capítol 1. Llenguatges formals i computació
1.1 Símbols, cadenes i llenguatges
1.1.1 Operacions amb cadenes
1.1.2 Operacions amb llenguatges
1.2 Generació de llenguatges
1.2.1 La jerarquia de Chomsky
1.2.2 Transformació de gramàtiques
1.2.3 Verificació de gramàtiques
1.3 Acceptació de llenguatges i computabilitat
1.4 Exercicis
Capítol 2. Autòmats finits i conjunts regulars
2.1 Tipus dautòmats finits
2.1.1 Autòmats indeterministes
2.1.2 Autòmats amb transicions buides
2.2 Autòmats finits i llenguatges regulars
2.2.1 Gramàtica equivalent a un autòmat finit
2.2.2 Autòmat equivalent a una gramàtica regular
2.3 Expressions regulars
2.3.1 Conjunts i expressions regulars
2.3.2 Propietats
2.3.3 Equivalències
2.3.4 Càlcul de lexpressió regular equivalent a un autòmat
2.4 Exercicis
Capítol 3. Propietats dels llenguatges regulars
3.1 Lema del bombament
3.1.1 Demostració de la no-regularitat
3.1.2 Problemes de decisió
3.2 Propietats de clausura
3.3 Teorema de Myhill-Nerode
3.3.1 Congruència associada a un llenguatge
3.3.2 Congruència associada a un autòmat
3.3.3 Una altra condició necessària per a la regularitat
3.3.4 Condició suficient per a la regularitat
3.3.5 Conseqüències i aplicacions
3.4 Minimització dautòmats
3.4.1 Equivalències entre estats
3.4.2 Autòmat associat a la relació dequivalència
3.4.3 Mètodes gràfics de càlcul de lautòmat mínim
3.5 Exercicis
Capítol 4. Gramàtiques incontextuals i autòmats amb pila
4.1 Introducció
4.2 Manipulació de gramàtiques incontextuals
4.2.1 Formes normals de Chomsky i Greibach
4.3 Autòmats amb pila
4.3.1 Criteris dacceptació
4.3.2 Autòmats deterministes i indeterministes
4.4 Relació entre llenguatges incontextuals i autòmats amb pila
4.4.1 Autòmat amb pila equivalent a una gramàtica incontextual
4.4.2 Gramàtica equivalent a un autòmat amb pila
4.4.3 Diferents tipus de llenguatges incontextuals
4.5 Propietats dels llenguatges incontextuals
4.5.1 Lema del bombament per als llenguatges incontextuals
4.5.2 Propietats de clausura
4.5.3 Problemes de decisió
4.6 El problema de lanàlisi en llenguatges incontextuals
4.6.1 Anàlisi descendent
4.6.2 Anàlisi ascendent
4.7 Exercicis
Capítol 5. La màquina de Turing
5.1 Definició de la màquina de Turing
5.1.1 La màquina de Turing com a acceptor de llenguatges
5.1.2 La màquina de Turing com a model de computació
5.2 Altres tipus de màquines de Turing
5.2.1 La màquina de Turing multipista i multicinta
5.2.2 La màquina de Turing amb cinta semiinfinita
5.2.3 La màquina de Turing modular
5.2.4 Catàleg de màquines modulars
5.2.5 La màquina de Turing indeterminista
5.3 Classes de llenguatges relacionades amb màquines de Turing
5.3.1 Llenguatges acceptats per màquines de Turing
5.3.2 Llenguatges generats per màquines de Turing
5.3.3 La màquina de Turing i la jerarquia de Chomsky
5.3.4 Codificació de màquines de Turing
5.3.5 La màquina de Turing universal
5.3.6 El llenguatge diagonal
5.4 Exercicis
Capítol 6. Resolubilitat
6.1 Resolució de problemes amb màquines de Turing
6.1.1 Funcions computables
6.1.2 Hipòtesi de Church-Turing
6.1.3 Relació entre llenguatges i problemes
6.2 Problemes resolubles i irresolubles
6.2.1 Reducció de problemes
6.2.2 El problema universal
6.3 Decidibilitat dalgunes propietats dels llenguatges recursivament enumerables
6.3.1 El problema del llenguatge buit
6.3.2 El teorema de Rice
6.4 El problema de la correspondència de Post
6.4.1 Enunciat
6.4.2 El problema de Post és indecidible
6.4.3 Problemes irresolubles sobre gramàtiques incontextuals. ...
6.5 El llenguatge de les computacions duna màquina
6.5.1 Definició
6.5.2 Aplicacions
6.5.3 Altres problemes irresolubles relacionats amb llenguatges incontextuals
6.6 Exercicis
Capítol 7. Introducció a la-completesa
7.1 Problemes tractables i intractables
7.2 Complexitats associades a màquines de Turing
7.2.1 Complexitat espacial i complexitat temporal
7.2.2 Complexitats i classes de llenguatges
7.3 Problemes -complets
7.3.1 Les classes P i
7.3.2 Reducció polinòmica
7.3.3 El teorema de Cook
7.4 Obtenció de problemes -complets
7.4.1 El recobriment exacte
7.4.2 El problema de la motxilla
7.5 Exercicis
Bibliografia
Apèndix A. Conceptes matemàtics preliminars
A.1 Conjunts
A.2 Estructures
A.3 Relacions
A.4 Aplicacions
A.5 Conjunts numerables
Apèndix B. Funcions recursives i computabilitat
B.1 Funcions numèriques i simbòliques
B.2 Aproximació recursiva a la computabilitat
B.2.1 Funcions inicials
B.2.2 Funcions recursives primitives
B.2.3 Funcions computables i no recursives primitives
B.2.4 Funcions p-recursives
B.3 Equivalència amb les funcions Turing computables
B.4 Exercicis
Índex analític
PRÒLEG
El present manual pretén donar una introducció als conceptes que constitueixen la base i els fonaments matemàtics de la computació.
A banda de servir de guia duna assignatura concreta que simparteix de forma molt similar en moltes universitats tant a nivell nacional com internacional, lobjectiu principal a lhora de proposar i desenvolupar aquest estudi ha estat donar una visió personal i adaptada als temps actuals duna disciplina aparentment allunyada de la pràctica de la informàtica.
Com reconeixen Hopcroft, Motwani i Ullman en la recent segona edició del seu famós llibre, les coses han canviat en els darrers vint anys i el que abans era una assignatura dels cursos més avançats i amb un caire marcadament matemàtic, ara se sol oferir en segon o tercer curs i amb la intenció (encertada) que són més importants els conceptes i les seues implicacions, que no el formalisme matemàtic emprat. Això no implica de cap manera que els conceptes shagen dimpartir (només) informalment. Precisament, en algunes titulacions dinformàtica, aquesta assignatura troncal és lúltima gran assignatura teòrica i shauria de prendre com una oportunitat per potenciar el formalisme matemàtic i el pensar abans de fer entre els futurs informàtics.
Lorganització és molt similar a altres llibres sobre autòmats i llenguatges. El capítol 1 conté una introducció general sobre el tipus denfocament que es presenta i introdueix les definicions relatives a símbols, cadenes i llenguatges. Aquest primer capítol i els tres següents es dediquen bàsicament a lestudi dels llenguatges regulars, els autòmats finits i les expressions regulars, així com a les gramàtiques incontextuals i els seus corresponents acceptors. La major part daquests conceptes tenen aplicació directa a lhora de construir compiladors, dissenyar llenguatges de programació o analitzar i processar cadenes de caràcters.
La resta de capítols, més que aplicacions, tenen conseqüències importantíssimes per entendre com i per què hi ha coses que no es poden calcular (capítols 5 i 6), i que hi ha càlculs que són possibles però no factibles (capítol 7). Al final sha inclòs una introducció a les funcions recursives en forma dapèndix, juntament amb un altre apèndix sobre conceptes matemàtics.
Molts dels exemples i exercicis proposats provenen dexàmens realitzats en els últims anys i sha intentat que cobresquen suficientment la totalitat de la matèria amb diversos graus de dificultat.
Aquest llibre ha estat planificat per ser utilitzat en una assignatura anual de 90 hores lectives i lúnic requisit són alguns coneixements bàsics dàlgebra i matemàtica discreta.
En algunes universitats (com una alternativa també vàlida) es dóna clarament més pes a la primera part en detriment de la segona, almenys quant a troncalitat. Fins i tot en aquest cas, el present llibre pot fer-se també servir, ja que conté bàsicament tots els conceptes escaients i amb el rigor suficient. Tan sols caldria ampliar lleugerament el nombre dexemples i problemes i potser ampliar el rigor i lextensió de les demostracions dalguns teoremes i les seues conseqüències quant a la primera part.
De ben diverses maneres aquest llibre ha rebut contribucions de moltes persones. De manera especial, i per proximitat acadèmica, de Salva Bayarri i dElena Díaz, així com dAriadna Fuertes. Alguns comentaris i discussions amb altres companys també han contribuït a donar forma i sentit a aquest llibre. Voldria anomenar Jesús Albert, Salva Moreno, Fernando Barber, Carlos Pérez, Juan Gutiérrez, Vicent Arnau, Gregorio Martín i, en general, tots els companys del Departament dInformàtica de la Universitat de València. Finalment, voldria citar els companys Encarna Segarra i Pedro García de la Universitat Politècnica de València i també Rafa Carrasco i Mikel Forcada de la Universitat dAlacant que han tingut lamabilitat de llegir parts substancials del manuscrit i de comentar amb mi els seus punts de vista.