• Descripció

Aquesta assignatura és el punt d'entrada al món de la Informàtica Teòrica en el sentit de disciplina que crea i explora fonaments teòrics a la recerca de les idees que permetin el posterior desenvolupament dels sistemes informàtics. Tradicionalment es distingeixen dos grans camps dins de la Informàtica Teòrica: la Teoria de Llenguatges Formals i les Teories de Calculabilitat i Complexitat. Aquí presentem una introducció al primer camp, la Teoria de Llenguatges Formals.

La problemàtica que s'estudia en aquesta assignatura és doble. En primer lloc, veurem com es pot descriure el conjunt de paraules que formen un llenguatge determinat. Aquesta problemàtica apareix, per exemple, al intentar descriure un llenguatge de programació o un idioma determinat. Es presenten dos mecanismes per descriure llenguatges, les expressions regulars i les gramàtiques independents del context.

Per altra banda, ens interessa que un ordinador sigui capaç de distingir les paraules que segueixen les regles d'un llenguatge de les que no les segueixen. Qualsevol aplicació que rebi una entrada en un cert format, ja sigui codi en un cert llenguatge de programació o una comanda en llenguatge natural, haurà de ser capaç de comprovar si l'entrada és correcta. Presentarem dos mecanismes per reconèixer de les paraules d'un llenguatge: els autòmats finits i els autòmats amb pila.

• Informació prèvia a la matrícula

Abans de cursar aquesta assignatura, es recomana haver cursat prèviament les assignatures de Lògica i Matemàtica Discreta.

• Objectius i competències

Els objectius que es pretenen que l'estudiant assoleixi amb l'assignatura són, resumidament:

 ·      Aprendre a construir autòmats finits que reconeguin llenguatges regulars i autòmats amb pila que reconeguin llenguatges incontextuals.

·      Conèixer la relació entre llenguatges, gramàtiques i autòmats tant en la classe dels llenguatges regulars com en la classe de llenguatges incontextuals, i saber passar amb destresa d'una forma de representació a l'altra.

·      Reconèixer a quina de les dues classes estudiades pertany un determinat llenguatge (o si no pertany a cap de les dues) sabent raonar el perquè.

·      Tenir una idea clara de les propietats principals que caracteritzen a les dues classes de llenguatges estudiats i aplicar-ho quan pertoqui.

 A més de tot això, considerem que els coneixements a assolir en aquesta assignatura han de formar part del bagatge cultural de tot enginyer informàtic. Està molt bé adquirir coneixements d'immediata aplicació pràctica però també és important conèixer part dels fonaments matemàtics en que s'aposenten i dels esdeveniments històrics més importants que els han permès. A més del seu valor intrínsec està demostrat que poden servir d'inspiració a efectes pràctics.

• Continguts

Mòdul 1: Introducció als llenguatges formals

El primer mòdul introdueix els conceptes i eines bàsiques per a poder treballar amb llenguatges formals que s'utilitzaran en els altres dos mòduls.

• Elements bàsics: alfabets, mots i llenguatges
• Operacions sobre mots
• Operacions sobre llenguatges
• Definició de llenguatges

Mòdul 2: Autòmats finits i llenguatges regulars

En el segon mòdul es caracteritza completament la classe dels llenguatges regulars. Es presenten els autòmats finits com a màquina abstracta que reconeix aquest tipus de llenguatges i es donen les pautes necessàries per obtenir qualsevol tipus d'autòmat finit, i a partir d'ell el seu equivalent mínim. Finalment es donen eines per poder demostrar la no regularitat d'un llenguatge.

• Autòmats finits deterministes i llenguatges regulars
• Autòmats finits indeterministes
• Operacions amb autòmats
• Minimització d'autòmats finits
• Expressions regulars
• Determinació de la no regularitat d'un llenguatge: el lema de bombament

Mòdul 3: Gramàtiques incontextuals i autòmats amb pila

En el tercer i darrer mòdul es caracteritza la classe dels llenguatges incontextuals. S'introdueix el concepte de gramàtica generativa i se'n distingueix els diferents tipus tot centrant-se en les gramàtiques incontextuals. I posteriorment s'estudia la màquina abstracta corresponent, l'autòmat amb pila. Com a l'anterior classe de llenguatges, s'acaba donant una propietat que permet demostrar la no incontextualitat d'un llenguatge.

• Definicions
• Arbre de derivació i ambigüetat
• Verificació de gramàtiques
• Simplificació de gramàtiques
• Formes normals
• Autòmats amb pila
• Propietats llenguatges incontextuals

• Llista dels materials de què disposa l'assignatura

• Materials

• Apunts de l'assignatura i exercicis d'autoavaluació en suport paper.

• Enunciats i solucions de les activitats realitzades en el semestre i en els semestres anteriors, que estaran disponibles a l'aula de l'assignatura.

• Materials complementaris proposats pels professors consultors a través de l'aula de l'assignatura.