University of Malta

Study-Unit Description
UOM Main Page
Apply - Admissions 2016
Campus Map button


TITLE Formal Languages and Automata

LEVEL 02 - Years 2, 3 in Modular Undergraduate Course


DEPARTMENT Computer Science

DESCRIPTION The study-unit will be dealing with the formal treatment of languages and automata (or machines) to recognize languages. The aims are to instill the basic notions of languages, grammars and automata using formal mathematical notation. These topics underpin the main concepts behind the design and development of programming language compilers and parsers.


- Formal languages and grammars.
- Regular languages: regular grammars, finite-state automata, regular expressions.
- Context-free languages: context-free grammars, pushdown automata.
- Closure properties of regular languages.

Study-unit Aims:

- Expose the student to various methods for specifying languages and to results relating to the equivalence of these methods.
- Apply rigorous mathematical techniques to prove properties about languages.
- Facilitate the understanding of how compilers/parsers work.

Learning Outcomes:

1. Knowledge & Understanding:

By the end of the study-unit the student will be able to:

- Specify the recognition of a language through mechanisms such as grammars, FSAs, PDAs etc.
- Understand the limits of certain language classes such as Regular Languages, Context-Free languages etc.
- Understand the equivalence between certain specification mechanisms.

2. Skills:

By the end of the study-unit the student will be able to apply inductive principles as means of:

- Specifying infinite but regular sets of objects.
- Specifying functions and operations over these sets.
- Perform proofs by induction on the regular structure defining these sets.

Main Text/s and any supplementary readings:

Main Texts:

- An Introduction to Formal Languages and Automata, Peter Linz, Jones and Bartlett Publishers, 2006.
- An Introduction to the Theory of Computation, Michael Sipser, PWS Publishing, 1997.
- A First Course in Formal Language Theory, V.J. Rayward-Smith, McGraw Hill, 1995.

ADDITIONAL NOTES Students taking this study-unit are assumed to have knowledge of the material covered in the following study-units:

- CPS1002;
- CPS1005;
- CPS1011;
- CPS2000;
- ICS1018.

STUDY-UNIT TYPE Lecture and Independent Study

Assessment Component/s Resit Availability Weighting
Assignment No 20%
Examination (2 Hours) Yes 80%

LECTURER/S Adrian Francalanza

The University makes every effort to ensure that the published Courses Plans, Programmes of Study and Study-Unit information are complete and up-to-date at the time of publication. The University reserves the right to make changes in case errors are detected after publication.
The availability of optional units may be subject to timetabling constraints.
Units not attracting a sufficient number of registrations may be withdrawn without notice.
It should be noted that all the information in the study-unit description above applies to the academic year 2017/8, if study-unit is available during this academic year, and may be subject to change in subsequent years.
Study-unit Registration Forms 2017/8


For Undergraduate (Day) and Postgraduate students.


Academic Advisors 2017/8


Academic Advisors for ICT 1st year students (Intake 2017/8), NOW available

Faculty of ICT Timetables


ICT Timetables are available from Here.

Health and Safety Regulations for Labs Form

The Faculty of ICT Health and Safety Regulations for Laboratories form can be found here



Log In back to UoM Homepage