| Autòmats i gramàtiques | Codi: 05.579 : 6 |
Una part molt important de la informació disponible avui en dia es troba disponible en format textual: pàgines web, fitxers de configuració, scripts, programes d'ordinador o fins i tot text en llenguatge natural. Per a que un ordinador pugui utilitzar aquesta informació, és necessari que la pugui interpretar d'acord a les regles del llenguatge en que està escrita.
En aquesta assignatura es presenten tècniques bàsiques per descriure l'estructura d'un llenguatge, les expressions regulars i les gramàtiques lliures de context. Aquestes notacions són les que es fan servir, per exemple, per descriure els llenguatges de programació o descriure patrons de text per fer cerques.
A més, es presenten els mecanismes que utilitzen els ordinadors per reconèixer si una sentència està correctament formada segons l'estructura d'un llenguatge. En concret es presenten els autòmats finits i autòmats amb pila.
En resum, aquesta assignatura proporciona les eines bàsiques per saber tractar informació textual amb un ordinador.
L'assignatura Autòmats i Gramàtiques es pot cursar com a assignatura optativa o bé com a part de l'itinerari de Computació.
Dins d'aquest itinerari, aquesta assignatura proporciona els conceptes bàsics per a l'anàlisi d'informació textual. Aquests coneixements s'apliquen a Compiladors a l'anàlisi dels llenguatges de programació. A més, juntament amb Intel·ligència Artificial i Aprenentatge computacional, l'assignatura proporciona les bases utilitzades en les tècniques del processament de llenguatge natural.
Per altra banda, el concepte d'autòmat com a màquines d'estat també s'utilitza en molts àmbits de la informàtica, com ara la descripció de sistemes hardware (Fonaments de computadors) i software (Enginyeria del programari).
Aquesta assignatura aporta els fonaments necessaris per qualsevol tasca que requereixi el tractament d'informació textual. En concret, aquestes competències són imprescindibles per treballar en la construcció de compiladors i intèrprets de llenguatges de programació o el tractament de llenguatge natural (comprensió de textos, reconeixement de veu, ...).
Per altra banda, els coneixements d'expressions regulars i gramàtiques també faciliten l'aprenentatge de nous llenguatges de programació, que sempre es descriuen utilitzant aquests formalismes.
Per últim, l'ús d'expressions regulars per descriure patrons de cerca és molt comú en diferents àmbits (editors de text, comandes del sistema operatiu per localitzar fitxers, cercadors d'internet, ...). Hi ha molts llenguatges de scripting i processament de documents de text com ara Perl, sed o awk que utilitzen de forma intensiva les expressions regulars per fer el tractament i manipulació de textos.
L'assignatura requereix coneixements bàsics del concepte de graf, que s'ha introduït en l'assignatura Grafs i Complexitat.
Per altra banda, l'assignatura requereix una certa habilitat amb l'ús de notació matemàtica, donat que els llenguatges es descriuen de manera formal. Per aquest motiu, es recomana haver cursat prèviament l'assignatura de Lògica.
Abans de cursar aquesta assignatura, és molt recomanable haver cursat prèviament les assignatures següents:
- Àlgebra
- Grafs i Complexitat
- Lògica
Les competències generals del Grau que es posen de manifest en aquesta assignatura són:
- Capacitat per utilitzar els fonaments matemàtics, estadístics i físics per comprendre els sistemes TIC.
- Capacitat per analitzar un problema en el nivell d'abstracció adequat a cada situació i aplicar les habilitats i coneixements adquirits per a resoldre'l.
Les competències específiques d'aquesta assignatura són:
- Saber definir els conceptes d'alfabet, mot i llenguatge.
- Conèixer les operacions sobre llenguatges i mots (concatenació, clausures) i saber utilitzar-les per descriure llenguatges complexos.
- Saber construir expressions regulars i gramàtiques independents del context per descriure un llenguatge donat.
- Saber construir autòmat finits i autòmats amb pila per reconèixer les paraules d'un llenguatge donat.
- Conèixer les relacions entre autòmats, expressions regulars i gramàtiques i saber passar d'una representació a l'altra amb destresa.
- Conèixer les diferències entre llenguatges regulars i independents de context i saber classificar un llenguatge a la família corresponent.
L'assignatura s'estructura en tres mòduls:
|
Mòdul |
Continguts |
Descripció |
|
1. Alfabets, mots i llenguatges |
1. Elements bàsics: alfabets, mots i llenguatges 2. Operacions sobre mots 3. Operacions sobre llenguatges 4. Definició de llenguatges |
En aquest mòdul es descriuen els elements que formen un llenguatge i les operacions per manipular-los. |
|
2. Autòmats finits i llenguatges regulars |
1. Autòmats finits deterministes i llenguatges regulars 2. Autòmats finits indeterministes 3. Operacions amb autòmats finits 4. Minimització d'autòmats finits 5. Expressions regulars 6. El lema de bombament |
Es presenta la classe de llenguatges més simples, els llenguatges regulars. Es proporciona un formalisme per descriure aquests llenguatges (expressions regulars) i un altre per reconèixer les paraules que en formen part (autòmats amb pila). |
|
3. Gramàtiques incontextuals i autòmats amb pila |
1. Conceptes introductoris 2. Arbre de derivació i ambigüitat 3. Verificació de gramàtiques 4. Simplificació d'una gramàtica 5. Formes normals 6. Autòmats amb pila 7. Propietats dels llenguatges incontextuals |
Es presenta una classe de llenguatges més complexos, anomenats independents del context. L'estructura d'aquest llenguatge es descriure mitjançant gramàtiques i les seves paraules es reconeixen mitjançant autòmats amb pila. |
| Teoria d'autòmates i llenguatges formals I |
Els mòduls didàctics constitueixen la part més important dels materials de l'assignatura que estan accesibles en format digital a l'aula virtual.
La Normativa acadèmica de la UOC disposa que el procés d'avaluació es fonamenta en el treball personal de l'estudiant i pressuposa l'autenticitat de l'autoria i l'originalitat dels exercicis fets.
La manca d'originalitat en l'autoria o el mal ús de les condicions en què es fa l'avaluació de l'assignatura és una infracció que pot tenir conseqüències acadèmiques greus.
Es qualificarà l'estudiant amb un suspens (D/0) si es detecta manca d'originalitat en l'autoria d'alguna activitat avaluable (pràctica, prova d'avaluació contínua (PAC) o final (PAF), o la que es defineixi al pla docent), sigui perquè ha utilitzat material o dispositius no autoritzats, sigui perquè ha copiat textualment d'internet, o ha copiat d'apunts, de materials, de manuals o d'articles (sense la citació corresponent), d'altres estudiants, o per qualsevol altra conducta irregular.
La qualificació de suspens (D/0) en les qualificacions finals d'avaluació contínua pot comportar l'obligació de fer l'examen presencial per a superar l'assignatura (si hi ha examen i si superar-lo és suficient per a superar l'assignatura segons indiqui el pla docent).
Quan aquesta mala conducta es produeixi durant la realització de les proves d'avaluació finals presencials, l'estudiant pot ser expulsat de l'aula, i l'examinador farà constar tots els elements i la informació relatius al cas.
D'altra banda, aquesta conducta pot donar lloc a la incoació d'un procediment disciplinari i l'aplicació, si escau, de la sanció que correspongui.
La UOC habilitarà els mecanismes que consideri oportuns per a vetllar per la qualitat de les seves titulacions i garantir l'excel·lència i la qualitat del seu model educatiu.
|
Aquesta assignatura es pot superar per una doble via: d'una banda a partir de l'avaluació contínua (AC), i d'altra banda, mitjançant la realització d'un examen final (EX). Per a fer l'EX no cal haver superat l'AC. La fórmula d'acreditació de l'assignatura és la següent: AC o EX. |