Course Catalog 2008-2009 International Basic Pori International Postgraduate Open University |Degrees|     |Study blocks|     |Courses|

Course´s person responsible

Keijo Ruohonen

Implementations

	Lecture times and places	Target group recommended to
Implementation 1

Requirements

Active participation in exercises and written solutions to homework exercises, or a closed-book written exam.
Completion parts must belong to the same implementation

Objectives

Introduction to the formal theory of languages and its connections to computability, algorithmics, etc.

Content

Content	Core content	Complementary knowledge	Specialist knowledge
1.	Basic properties of formal languages, Chomsky hierarchy of grammars. Recognition of languages by automata (FA, PDA, LBA, TM). Lindenmayer systems. Code theory (codes, prefix codes, bounded-delay codes, optimal codes, Huffman coding). Formal power series (multilanguages, stochastic languages, quantum languages).

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

Correspondence of content

More precise information per implementation

	Description	Methods of instruction	Implementation
Implementation 1		Excercises Practical works	Contact teaching: 0 % Distance learning: 0 % Self-directed learning: 0 %

Last modified	14.04.2009
Modifier	Keijo Ruohonen