TIEA241 Automatons and Formal Languages

Academic Year 2013–2014 — self-study course

You can take this course through independent study. Unfortunately, the English material is a bit rougher than the material we have available in Finnish. For the Finnish version, see the Finnish page.


First, enroll in this course through Korppi.

Then, read both of the following works to the indicated extent:

I recommend that you work through at least some of the exercises and problems included in the books.

Finally, choose one of the following options.

Option A: Textbook exam

Register to an exam of this course in Korppi and send me an email message letting me know. Then take the exam normally (do not bring the textbooks with you).

Exams: 29th November 2013, 18th December 2013, 21st March 2014, 21st May 2014, 13th June 2014, and 11th July 2014.

Option B: Practical project

A practical project consists of a programming task and a written essay.

The project must be submitted for grading no later than June 15, 2014.


The programming task is to create a computer program in which the automata (mainly finite automata, push-down automata or Turing machines) or the grammar formalisms (mainly context-free grammars) at issue in this course are a significant part of the implementation. Typically, such programs process natural or computer languages, and text adventure games have been a popular topic in this course.

The program must be compilable in the computer classrooms at Agora, or by using freely installable programs under Linux.

The essay must provide instructions for compiling the program from source code as well as any essential usage instructions. It must also discuss the essentials of the program's implementation, taking special care to address how automata or grammar formalisms have been used in the program. The essay must also discuss how computability (decidability) issues are relevant to the program, or argue in detail why they are not relevant. The typical length of such an essay is about five pages.

You may prepare the project alone or with one partner. In the latter case, both of you must participate in writing both the program and the essay, and the essay must briefly discuss who did what.


Suggested topics are: a text-based adventure game (interactive fiction); an Eliza-style chatterbot; or a simple parser generator.

You should discuss with me the topic of your program before starting.


Submit your program as a zip or tar.gz attachment to an email to antti-juhani.kaijanaho@jyu.fi. Do include source code. Do not include any compiled code (exe, jar, class, obj, o, etc).

The essay shall be submitted by email using the Urkund plagiarism detection tool. Please email me for submission instructions.


Minimum requirements (grade 1) for the project are as follows:

A good project (grade 3) also exhibits the following traits:

An outstanding project (grade 5) fulfils all the criteria for lower grades and additionally either has no issues worth mentioning or exceeds expectations for a project in this course in at least some aspects.

If a project has multiple authors, they will ordinarily receive a common grade for the project. The number of authors will influence grading.

The difficulty of the chosen project topic will be taken into account in grading.

If you have questions, feel free to contact me.

2014-05-26 antti-juhani.kaijanaho@jyu.fi