Course Catalog 2012-2013
International

Basic Pori International Postgraduate Open University

|Degrees|     |Study blocks|     |Courses|    

Course Catalog 2012-2013

MAT-41186 Formal Languages, 6 cr

Additional information

This is a self-study course.
Suitable for postgraduate studies

Person responsible

Keijo Ruohonen

Lessons

Study type P1 P2 P3 P4 Summer Implementations Lecture times and places
            MAT-41186 2011-01  

Requirements

Closed-book written exam.
Completion parts must belong to the same implementation

Learning outcomes

After completing the course the student is able to define the basic families of formal languages and their generation and recognition methods. The student masters basic operations on languages and their properties, in particular in connection with the basic families. The student is also able to classify simple languages into the basic families. Completing the course gives the student tools for analyzing syntactically languages in applications, e.g. programming languages, simple models of natural languages, codes and, in a restricted sense, also various generalizations of languages (multilanguages, stochastic languages, quantum languages, fuzzy languages). Such tools have been extensively developed and investigated for a long time, and therefore it is simply not possible to include outcomes for them all within a single course. Completing the course the student nevertheless should be able the generalize and extend the skills.

Content

Content Core content Complementary knowledge Specialist knowledge
1. Basic properties and operations of formal languages. Regular expressions and languages with their basic properties. Finite automata and their basic properties. Pumping of regular languages. Minimization of finite automata.  Classification of a language as a regular or a nonregular language. Closure properties of regular languages under given operations.   
2. Chomsky types of grammars and languages (regular, context-free, context-sensitive and computably enumerable languages) and their basic properties.     
3. Context-free grammars and languages with their basic properties. Pushdown automata and their basic properties. Normal forms of context-free grammars. Pumping of context-free languages. Unambiguity and parsing of context-freegrammars.  Classification of a language as context-free or a non-context-free. Closure properties of context-free languages under given operations.  Undecidability results for context-free languages. The Post Correspondence Problem. 
4. Context-sensitive grammars and languages and length-increasing grammars with their basic properties. Normal forms. Linear-bounded automata and their basic properties. computably enumerable languages and Turing machines with their basic properties. The concept of computability.  Classification of a language as context-sensitive or a non-context-sensitive. Variants of Turing machines.   
5. Codes and their basic properties. The Sardinas-Patterson algorithm and its application in simple cases. Prefix codes and bounded-delay codes. The Huffman encoding algorithm and its application in simple cases.   Application of the Huffman algorithm in more complex cases.   
6. Lindenmayer systems and their basic properties.  Classification of languages into various L-families.   
7. Formal power series and their basic properties and operations. Example cases: multilangiages, stochastic languages, quantum languages and fuzzy languages.     

Evaluation criteria for the course

Final grade is determined from tutorial activity and the final closed-book exam. Passing the course requires passing the final exam, and for this at most half of the maximum points are required. Bonus points obtained by tutorial activity may be used to add the exam points according to a given scheme. A thorough mastering of the core content should be sufficient for passing the course with grade 3. To get the degree 4 at least some complementary knowledge is usually required, getting the grade 5 then requires a more thorough mastering of this knowledge.

Assessment scale:

Numerical evaluation scale (1-5) will be used on the course

Partial passing:

Completion parts must belong to the same implementation

Study material

Type Name Author ISBN URL Edition, availability, ... Examination material Language
Book   Introduction to Languages and the Theory of Computation   Martin, J.C.            English  
Book   Theory of Formal Languages with Applications   Simovici, D.A. & Tenney, R.L.            English  
Other online content   Home page   Ruohonen, K.            English  
Summary of lectures   Formal Languages   Ruohonen, K.            English  

Prerequisite relations (Requires logging in to POP)



Correspondence of content

Course Corresponds course  Description 
MAT-41186 Formal Languages, 6 cr MAT-41180 Formal Languages, 6 cr  

More precise information per implementation

Implementation Description Methods of instruction Implementation
MAT-41186 2011-01        

Documents

FL.pdf

Last modified24.01.2012