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