Course Details for A.Y. 2013/2014

The information on this page refer to the academic year 2013/2014. Therefore, several links are not available and data may be incomplete. To read the current information on the course, if it is still available, go to the university course catalogue . To read information relating other academic years, use the list at the bottom of this page.

A. Year:

2013/2014

Name:

Fondamenti dell'informatica II / Foundations of Computer Science II

Type:

Course

Basic information

Code:

F0196

Sector:

INF/01

Credits:

: Laurea Magistrale in Informatica 6 CFU (b)

Term:

1° semestre

Degree(s):

Laurea Magistrale in Informatica curriculum GSEEM Opzionale
Laurea Magistrale in Informatica 2° anno curriculum Generale Obbligatorio

Language:

English

Teacher(s):

Sergio Orefice

Course Objectives

The course offers students an in-depth overview of automata and formal language theory, and an introduction to non linear languages

Course Content

1. Formal language basic notions. Chomsky hierarchy
2. Finite automata. Nondeterministic finite automata. Finite automata with epsilon-moves
3. Regular expressions. The Kleene theorem. Pumping Lemma for regular sets. Properties of regular sets
4. Context-free grammars. Pushdown automata. Properties of context-free languages. Chomsky Normal Form. Pumping Lemma for context-free languages. The CYK algorithm
5. Nonlinear and visual formal languages. Syntactical models
6. Context-free positional grammars

Learning Outcomes (Dublin Descriptors)

On successful completion of this course, the student should

have knowledge of the main formalisms of automata and formal language theory, have knowledge and understanding of the various characterizations of regular and context free languages
understand and apply properties of regular and context free languages, demonstrate capacity to extend concepts and formalisms of classic formal language theory to the specification of the syntax of non linear languages
demonstrate skill in formal reasoning and ability to conceive a proof
understand and explain language specifications by using formal notations (regular expressions, automata, grammars)
demonstrate capacity for reading and understanding texts and scientific papers using notions learnt by the course and understand their applications

Prerequisites and Learning Activities

Knowledge of basic courses of programming, familiarity with common data structures, recursion and basic concepts of compilers

Assessment Methods and Criteria

Written examination (midterm + final) on the subjects treated inthe course

Textbooks

Hopcroft, Motwani, Ullman, Automi, Linguaggi e calcolabilità , Addison-Wesley. Reference for points 1-4
Hopcroft, Motwani, Ullman, Introduction to Automata Theory, Languages and Computation , Addison-Wesley. Reference for points 1-4
Papers provided by the lecturer Reference for points 5-6

Internet Resources

Homepage:

http://www.di.univaq.it/orefice/fond.html

Course page updates

This course page is available (with possible updates) also for the following academic years:

To read the current information on this course, if it is still available, go to the university course catalogue .

Course information last updated on: 25 febbraio 2014, 12:13