University of Malta
 

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


CODE CPS2005

 
TITLE Formal Languages and Automata

 
LEVEL 02 - Years 2, 3 in Modular Undergraduate Course

 
ECTS CREDITS 5

 
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.

Syllabus:

- 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

 
METHOD OF ASSESSMENT
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.
Calendar
Notices
Study-unit Registration Forms 2017/8

Register

For Undergraduate (Day) and Postgraduate students.

 

Faculty of ICT Timetables

Timetables

ICT Timetables are available from Here.

Health and Safety Regulations for Laboratories Form

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

 HealthAndSafety

13th Edition of EY’s Annual Attractiveness Event

 Logo

 

 

The 13th Edition of EY’s Annual Attractiveness event will be held on 25th October 2017 at the InterContinental Hotel,

St. Julians. It is titled "Thinking without the box: disruption, technology and FDI".

 

The  students' invitation and more information can be found here

The conference programme can be found here

 

 
 

Log In back to UoM Homepage