Inizio della pagina -
Logo DISCO
|
Visita la Versione ad elevata leggibilità
|
Vai al Contenuto della pagina
|
Vai alla Fine dei contenuti
|
Vai al Menu Principale
|
Vai alla Barra di navigazione (sei in)
|
Vai al Menu di navigazione (albero)
|
Vai alla Lista dei comandi
|
Vai alla Lista degli approfondimenti
|
Vai al Menu inferiore
|
Logo Ateneo
   
Didattica
Linguaggi e computabilità

Codice ins.

Insegnamento

CFU ins.

Tipo ins.

Anno

Sem.

SSD ins.

Responsabile insegnamento

E3101Q111

Linguaggi e computabilità

8

OBB

2

1

INF/01

SIMONE Carla

 

Languages and Computability

 

 

 

 

 

 

Docente turno A-L: Simone Carla
Docente turno M-Z: Pomello Lucia

Contenuti:
Automi a stati finiti, linguaggi regolari e espressioni regolari. Linguaggi e grammatiche libere da contesto e automi a pila. Elementi di computabilità: la macchina di Turing; la tesi di Church-Turing; la macchina di Turing Universale. Problemi non risolvibili.  Linguaggi di mark-up e di serializzazione e loro relazione con le grammatiche.

Obiettivi formativi:
L’insegnamento ha l’obiettivo di mettere in relazione elementi della teoria dei linguaggi formali con le basi dell'analisi lessicale e sintattica dei linguaggi di programmazione e di rendere lo studente consapevole dei limiti della computazione.  Lo studente sarà in grado di definire grammatiche regolari e libere da contesto che sono necessarie per l’utilizzo di analizzatori sintattici standard.

Prerequisiti:

Concetti di base di programmazione (Programmazione 1 e 2) e di informatica teorica (Fondamenti dell’Informatica)

Metodi didattici:

Lezioni ed esercitazioni in aula, uso dei laboratori per gli aspetti sperimentali, attività di studio individuale supportate da materiali didattici in e-learning.

Altre informazioni:

Programma esteso:

  • Automi a stati finiti deterministici
  • Automi a stati finiti  non deterministici con epsilon-transizioni
  • Espressioni e linguaggi regolari
  • Automi a stati finiti ed espressioni regolari
  • Proprietà algebriche per i linguaggi regolari
  • Pumping Lemma per linguaggi regolari
  • Chiusura di linguaggi regolari rispetto ad operazioni booleane
  • Equivalenza e minimizzazione di automi a stati finiti
  • Grammatiche regolari e libere da contesto (CFG)
  • Alberi sintattici
  • Ambiguità  nelle Grammatiche e nei Linguaggi
  • Automi a Pila  (PDA) e  loro linguaggi
  • Equivalenza tra PDA e CFG
  • Automi a Pila Deterministici
  • La Macchina di Turing e le sue architetture
  • Linguaggi non Ricorsivamente Enumerabili, Ricorsivamente Enumerabili  e Ricorsivi
  • Problemi indecidibili e decidibili
  • I linguaggi di mark-up e di serializzazione (HTML, XML, YAML, Jason) e loro applicazioni

 

Testi di riferimento:
J.E. Hopcroft, R. Motwani, J.D. Ullman, Automi, linguaggi e calcolabilita’, Addison Wesley, Terza Edizione

Modalità di verifica dell'apprendimento:
Tipo esame:
Scritto e orale separati

Tipo valutazione:
Voto finale

Contents:
Finite automata, regular languages and regular expressions. Context-free languages, context-free grammars and pushdown automata. Elements of the theory of computation: Turing machine, the Church-Turing thesis, the universal Turing machine, unsolvable problems.  Mark-up and serialization languages and their relation with grammars.

Aims:
The course aims at putting in relation formal language theory with the parsing of programming languages and to make the student aware of the limits of computing. The student will be able to define regular and context-free grammars that are necessary to use standard parsing tools.

Prerequisites:
Basic concepts of programming (Programing 1 e 2) and of theoretical computer science (Foundations of Computer Science)

Detailed program:

  • Deterministic Finite State Automata
  • Non Deterministi Finite State Automata with  epsilon moves
  • Regular Languages and Regular Expressions
  • Finite Automata and Regular Expressions
  • Algebraic properties of regular Languages
  • Pumping Lemma for Regular Languages
  • Closure of boolean operators for Regular Languages
  • Equivalence and minimization of Finite State Automata
  • Regular and Context-free Grammars (CFG)
  • Parsing trees
  • Grammars and Languages ambiguity
  • Push Down Automata (PDA) and their languages
  • Equivalence of  PDA and CFG
  • Deterministic Push Down Automata
  • Turing Machine and its architectures; Universal Turing Machine
  • Non Ricursively Enumerable, Ricursively Enumerable e Recursive Languages
  • Decidable and undecidable problems
  • Mark-up and serializzation languages (HTML,XML,YAML, Jason)  and their applications

Teaching method:
Lessons and practical exercises, use of laboratories for experimental activities, learning activities supported by e-learning teaching materials.

Teaching material:
J.E. Hopcroft, R. Motwani, J.D. Ullman, Automi, linguaggi e calcolabilita’, Addison Wesley, Terza Edizione

Modalità di verifica dell'apprendimento:

Tipo esame:
Scritto e orale separati
Prove parziali sulle unità didattiche

Tipo valutazione:
Voto finale

Approfondimenti

Google Translate
Translate to English Translate to French Translate to German Translate to Spanish Translate to Chinese Translate to Portuguese Translate to Arabic
Translate to Albanian Translate to Bulgarian Translate to Croatian Translate to Czech Translate to Danish Translate to Dutch Translate to Finnish Translate to Greek Translate to Hindi
Translate to Hungarian Translate to Irish Translate to Japanese Translate to Korean Translate to Norwegian Translate to Polish Translate to Romanian Translate to Russian Translate to Serbian
Translate to Slovenian Translate to Swedish Translate to Thai Translate to Turkish

(C) Copyright 2016 - Dipartimento Informatica Sistemistica e Comunicazione - Viale Sarca, 336
20126 Milano - Edificio U14
redazioneweb@disco.unimib.it - ultimo aggiornamento di questa pagina 11/11/2013