Course Catalog 2007-2008

MAT-41186 FORMAL LANGUAGES, 6 cr
Formal Languages

Courses persons responsible
Keijo Ruohonen

Lecturers
Keijo Ruohonen

Implementations
Programs: Electrical Engineering, Information Technology, Automation Engineering, Communications and Electronics, Science and Engineering, Biotechnology
  Period 1 Period 2 Period 3 Period 4 Period 5 Summer
Exercise 2 h/week 2 h/week - - - -
Exam  
(Timetable for academic year 2007-2008)

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)        

Requirements for completing the course
Active participation in exercises and written solutions to homework exercises, or a closed-book written exam.

Evaluation criteria for the course

  • Used assessment scale is numeric (1-5)

    • Study material
    Type Name Auhor ISBN URL Edition, availability... Exam material Language
    Lecture slides Formaalit kielet Ruohonen, K.   http://math.tut.fi/~ruohonen/FK.pdf   No  Finnish 
    Book Theory of Formal Languages with Applications Simovici, D.A. & Tenney, R.L.       No  English 
    Book Introduction to Languages and the Theory of Computation Martin, J.C.       No  English 

    Prerequisites
    Code Course Credits M/R
    MAT-21160 MAT-21160 Mathematics for Algorithms 3 Recommendable

    Prequisite relations (Sign up to TUT Intranet required)

    Remarks

    The course is lectured biennially.

  • The course is suitable for postgraduate studies.

    • Distance learning

  • ITC utilized during the course

    • - In information distribution via homepage, newsgroups or mailing lists, e.g. current issues, timetables
    - In compiling teaching material, particularly for online use or other electronic media
    - In distributing and/or returning exercise work, material etc
    - In the visualization of objects and phenomena, e.g. animations, demonstrations, simulations, video clips

    Scaling
    Methods of instructionHours
    Exercises 48
    Assignments 96
    Total sum 144

    Correspondence of content
    MAT-41180 Formal Languages

    Course homepage

    Last modified 16.02.2007
    Modified byKeijo Ruohonen