Course Details for A.Y. 2016/2017
Name:
Fondamenti dell'informatica II / Foundations of Computer Science II
Basic information
Credits:
: Master Degree in Computer Science 6 CFU (b)
Degree(s):
Master Degree in Computer Science curriculum GSEEM Elective
Master Degree in Computer Science 2nd anno curriculum General Compulsory
Language:
English
![[info]](img/info16.png)
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
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. 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
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: 03 febbraio 2015, 12:24
Italian version
sad
strutture.univaq