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

Person responsible

Keijo Ruohonen

Implementations

	Lecture times and places	Target group recommended to
Implementation 1	Per 1, 2 : Wednesday 12 - 14, Tb223 Friday 10 - 12, Tb223

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

Learning outcomes

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			Contact teaching: 0 % Distance learning: 0 % Self-directed learning: 0 %

Last modified	14.04.2009
Modifier	Keijo Ruohonen