|
|
|||||||||||||||||
Course Catalog 2011-2012
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 |
| |
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:
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 |
|
|
|
More precise information per implementation
| Implementation | Description | Methods of instruction | Implementation |
Documents