This site uses only proprietary and third party technical cookies. By continuing to browse the site you are agreeing to our use of cookies. I agree I want to find out more

Browse the Department site:

Browse the Teaching site:

Course Details for A.Y. 2010/2011

The information on this page refer to the academic year 2010/2011. 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:

2010/2011

Name:

Fondamenti dell'informatica II / Foundations of Computer Science II

Type:

Course

Basic information

Code:

F1I023

Sector:

INF/01

Credits:

: 6 CFU (b)

Term:

2° semestre

Degree(s):

Laurea Magistrale in Informatica curriculum SDRC Opzionale
Laurea Magistrale in Informatica curriculum ASSC Opzionale
Laurea Magistrale in Informatica curriculum GSEEM Opzionale

Language:

Italian

Teacher(s):

Sergio Orefice

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. Syntactical analysis of nonlinear languages

Textbooks

Hopcroft, Motwani, Ullman, Automi, Linguaggi e calcolabilità , Addison-Wesley. Riferimento per i crediti 1-4
Hopcroft, Motwani, Ullman, Introduction to Automata Theory, Languages and Computation , Addison-Wesley. Riferimento per i crediti 1-4
Materiale fornito dal docente Riferimento per i crediti 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: 26 maggio 2011, 11:06

About Us

The DISIM represents an internationally recognized pole for teaching and research in Information Engineering, advanced Informatics, and pure and applied Mathematics.

Quick Links

Get in Touch with Us

Via Vetoio, Coppito, 67100 L'Aquila

disim

sad

strutture.univaq

+39 0862 433002

+39 0862 433180 (fax)