Course Details for A.Y. 2019/2020

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

2019/2020

Name:

Teoria dei Linguaggi / Theory of Languages

Type:

Course

Basic information

Code:

DT0269

Sector:

INF/01

Credits:

: Master Degree in Computer Science 6 CFU (b)
: Bachelor Degree in Computer Science 6 CFU (b)

Term:

2^nd semester

Degree(s):

Bachelor Degree in Computer Science 3^rd anno curriculum General Elective
Master Degree in Computer Science 2^nd anno curriculum NEDAS Elective
Master Degree in Computer Science 2^nd anno curriculum SEAS Elective
Master Degree in Computer Science curriculum UBIDIS Elective

Language:

Italian

Teacher(s):

Sergio Orefice

Course Objectives

The course offers students an in-depth overview of formal language theory

Course Content

- Introduction to language theory: Formal language basic notions. Chomsky hierarchy.
- Regular languages: Formalisms (DFA, NFA, epsilon-NFA, regular expressions). Equivalence results (subset construction, Kleene theorem, Thompson algorithm). Pumping Lemma. Closure properties. Decision properties (testing emptiness, testing membership, testing equivalence).
- Context-free languages: Formalisms (context-free grammars, PDA, DPDA). Chomsky Normal Form. Pumping Lemma. Closure properties. Decision properties (testing membership: CYK algorithm).

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
understand and apply properties of regular and context free 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 other texts on related topics

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

Formative assessment: the formative assessment is performed via interaction between teacher and students during lectures. The students are encouraged to actively participate to the lectures by making questions and discussing the theoretical concepts presented and the solutions adopted in the developed examples. Summative assessment: written test on the subjects treated in the course. An optional mid-term written test will also be provided, which is meant to cover the first part of the course, in order to help the students to split the workload. The written test (lasting 2 hours) consists of a set of questions for the verification of theoretical/formal competences and for the verification of skills in understanding and solving significant exercises. Criteria of evaluation will be: the level of knowledge of the notions and formalisms presented in the course, as well as the ability to apply them; the clarity and completeness of explanations.

Textbooks

Hopcroft, Motwani, Ullman, Automi, Linguaggi e Calcolabilità , Addison-Wesley.

Internet Resources

Homepage:

http://www.di.univaq.it/orefice/corsi.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: 21 ottobre 2016, 10:35