Llenguatges, Gramàtiques i Autòmats (LGA)
| Professors Responsables: |
RAFEL CASES MUÑOZ (cases lsi.upc.edu)
|
|
Crèdits: 4.5 (3.0 T 1.5 P 0.0 L)
| |
Departament:
LSI
|
Tipus d'assignatura
Obligatoria de primer cicle per la EI
Obligatoria per la ETIS
Optativa per la ETIG
Requisits de l'assignatura
|
IL
- Pre-correquisit per la EI , ETIG , ETIS
|
|
|
MD
- Pre-correquisit per la EI , ETIG , ETIS
|
|
|
PM
- Pre-correquisit per la EI , ETIG , ETIS
|
|
Objectius docents
Donar una introducció a alguns temes de rellevància en
informàtica teòrica, a ser complementats per l'assignatura MAC.
Es pretén que els estudiants manegin els elements bàsics per a
l'estudi de la teoria de llenguatges i autòmats, tenint en compte
també l'ús que d'aquesta teoria es farà a l'assignatura de
compiladors.
Els estudiants, després de cursar aquesta assignatura, haurien de
conèixer els diferents graus de complexitat intrínsecs dels
llenguatges regulars i incontextuals, i conèixer l'existència de
classes més àmplies. Disposaran també d'algunes eines per
descriure aquests llenguatges, per reconèixer-los, i per
caracteritzar-los.
Programa
1. Llenguatges formals
1. Introducció
2. Alfabets i mots
3. Operacions amb mots
4. Llenguatges. Concatenació
5. Altres operacions amb llenguatges
6. Morfismes i substitucions
2. Gramàtiques incontextuals.
1. Introducció
2. Definició
3. Arbre de derivació. Ambigüitat
4. Verificació de gramàtiques
5. Operacions bàsiques amb gramàtiques
3. Normalització de gramàtiques
1. Introducció
2. Eliminació de produccions nul·les
3. Eliminació de produccions unàries
4. Eliminació de símbols inútils
5. Gramàtiques depurades
6. Forma normal de Chomsky
4. Autòmats finits.
1. Introducció
2. Autòmats finits deterministes
3. Verificació d'automats finits
4. Autòmats finits indeterministes
5. Equivalència dels NFA's amb els DFA's
6. Operacions bàsiques amb autòmats
7. Llenguatges no regulars
5. Minimització d'autòmats finits
1. Minimització d'un DFA
2. Algorisme de minimització
3. Sobre la talla del DFA mínim
4. Equivalència entre autòmats
6. Expressions regulars i gramàtiques regulars
1. Introducció
2. Expressions regulars
3. Equacions lineals entre llenguatges. Lema d'Arden
4. Sistemes d'equacions lineals associats a un NFA
5. Gramàtiques regulars
6. Correspondència entre gramàtiques regulars i autòmats finits
7. Morfismes i substitucions de llenguatges regulars
7. Propietats d'iteració
1. Lema de bombament de llenguatges regulars
2. Lemes de bombament de llenguatges incontextuals
8. Autòmats amb pila
1. Introducció
2. Autòmats amb pila deterministes
3. Autòmats amb pila indeterministes
4. Equivalència entre autòmats amb plia i gramàtiques incontextuals
5. Propietats de tancament dels CFLs i dels DCFLs
9. Autòmats bidireccionals
1. Introducció
2. Autòmats finits bidireccionals
3. Autòmats amb pila bidireccionals
10. Sinopsi del curs
1. Introducció
2. Relació entre les famílies de llenguatges estudiades
3. La jerarquia de Chomsky
Avaluació
La nota final (F) té dues components additives: una component
de la part teòrica (T) i una component de la part de problemes (P).
Determinació de la component teòrica:
-------------------------------------------------------------
Cap a mitjans del quadrimestre es passarà una prova de la part del
temari que s'hagi estudiat fins a aquell moment. En acabar el curs es
passarà una prova de la totalitat del temari.
La nota corresponent a la part teòrica s'obté així:
....... Sigui N1 la nota sobre 10 de la prova parcial.
....... Sigui N2 la nota sobre 10 de la prova final.
....... Sigui N3 la mitjana aritmètica de N1 i N2.
............... T = MAX{N2 , N3}
Determinació de la component de problemes:
------------------------------------------------------------------------
Hi ha possibilitat de resoldre uns exercicis, l'enunciat dels quals
es farà públic al llarg del curs. La nota que s'obté amb aquests
exercicis, que pot sumar un màxim d'un punt, és la component P.
Determinació de la nota final:
-----------------------------------------------
Si la component teòrica és com a mínim de 3,5, s'obté la nota final
sumant les components teòrica i pràctica, sense que el resultat pugui
superar el 10. Es a dir:
............... F = MIN{10 , T+P}
Però si la component teòrica no arriba a 3,5, la nota final serà T.
Càrrega
D'acord amb el pla d'estudis corresponen a aquesta assignatura 4.5
crèdits (3 hores/setmana) repartits en 3 crèdits de teoria (2
hores/setmana) i 1.5 crèdits de problemes (1 hora/setmana).
Idealment, veiem les classes de teoria com a vehicle dels conceptes
bàsics i primers exemples, i les de problemes com a oportunitat de
discutir l'aplicació d'aquesta teoria amb més deteniment.
Informació complementària
Al document "LGA: Material de treball repartit per setmanes", que apareix
a la seccio d'avisos i notes, trobareu una especificació del treball a efectuar
cada setmana per seguir amb un bon aprofitament aquesta assignatura.
Allà hi consta la part de teoria que correspon a cada setmana, i uns
pocs exercicis per a treball personal. Es recomana
d'estudiar, setmana a setmana, la teoria proposada. També s'aconsella
de resoldre els exercicis plantejats.
|
