Back to department main page
Sitemap | Staff | SignIn Sign In
Home>Study Programmes>Bachelor in Applied Computer Science>Courses>Formal Languages - 2009/2010 - Computer Science
COURSE PRESENTATION FORM - FORMAL LANGUAGES - 2009/2010


COURSE NAME: Formal Languages

COURSE CODE: 70100

LECTURER: Diego Calvanese

TEACHING ASSISTANT: To be determined

TEACHING LANGUAGE: English

CREDIT POINTS: 4

LECTURE HOURS: 24

EXERCISE HOURS: 12

TIMESPAN: 28.09.2009 - 23.01.2010

TIMETABLE: see Timetable Page

OFFICE HOURS LECTURER: See http://www.inf.unibz.it/~calvanese/teaching/

OFFICE HOURS TEACHING ASSISTANT: Time to be determined - Via Sernesi 1, office C 5.01


PREREQUISITES
There are no prerequisites in terms of courses to attend.
Students should be familiar with notions of mathematics and set theory, as taught in the mathematics courses of the first year.

OBJECTIVES
The main objective of the Formal Languages course is to introduce the fundamental notions about formal languages and the mechanisms for representing them. The course will focus on the formal languages that find most applications in computer science, namely regular and context-free languages. Students should become familiar with the fundamental representation mechanism for such languages, which span machine-based models (finite state machines for regular languages), algebraic models (regular expressions), and generation-based models (formal grammars). The aim is to exploit such representation mechanisms to study the properties of the different types of formal languages and the main algorithms for processing languages, which help to solve problems that are of practical relevance.
A second objective of the course is to get students acquainted to a formal, rigorous approach in computer science.

SYLLABUS
  • Theory of regular languages
  • Dterministic and non-deterministic finite automata
  • Regular expressions
  • Regular grammars
  • Theory of context-free languages
  • Context-free grammars
  • Formal grammars


TEACHING FORMAT
Frontal lectures; exercises in class.

ASSESSMENT
Written or oral final examination (100% of mark).

READING LIST
Textbook:
  • Introduction to Automata Theory, Languages, and Computation (3rd edition). J.E. Hopcroft, R. Motwani, J.D. Ullman. Addison Wesley, 2007.
Further reading material for students interested in alternative viewpoints on the course material:
  • Elements of the Theory of Computation (2nd edition). H.R Lewis, C.H. Papadimitriou. Prentice Hall. 1998.
  • Introduction to the Theory of Computation. M. Sipser. PWS Publishing Company. 1997.


    SOFTWARE USED
    JFLAP, http://www.jflap.org/

    LEARNING OUTCOME
    Upon successful completion of the course, students will understand the general concepts of formal languages (specifically regular and context-free languages) and formal grammars, and algorithms and techniques used to process them.
    These competences are a prerequisite to other courses, such as Compilers.

    COURSE PAGE
    http://www.inf.unibz.it/~calvanese/teaching/fl/
Credits
© UniBz