| CODE | CPS2005 | ||||||||||||
| TITLE | Formal Languages and Automata | ||||||||||||
| UM LEVEL | 02 - Years 2, 3 in Modular Undergraduate Course | ||||||||||||
| MQF LEVEL | 5 | ||||||||||||
| 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 |
|
||||||||||||
| LECTURER/S | Adrian Francalanza (Co-ord.) |
||||||||||||
|
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 description above applies to study-units available during the academic year 2023/4. It may be subject to change in subsequent years. |
|||||||||||||