Finite automata and formal languages

The course is compulsory within the Computer Science, Bachelor's Programme (N1COS).

The course can be part of the following programmes:

1. Computer Science, Master's Programme (N2COS)
2. Mathematical Sciences, Master's Programme (N2MAT)
3. Bachelor's Programme in Mathematics (N1MAT)

The course is a also a single-subject course at Gothenburg University.

To be eligible for this course, students must have successfully completed 45 credits in computer science or mathematics, including the following courses:

• 7.5 credits in discrete mathematics (for example DIT984, MMG200 or equivalent)
• 7.5 credits in programming (for example DIT441, DIT143, DIT013, DIT948, DIT953, MVG200 or equivalent)

Applicants must prove knowledge of English: English 6/English level 2 or the equivalent level of an internationally recognized test, for example TOEFL, IELTS.

The course's main topics are finite automata, regular expressions and context-free grammars. It also contains a short introduction to Turing machines.

Finite automata and regular expressions are simple models of computation. They are for instance used to control traffic lights, to search for patterns, and for lexical analysis. Furthermore their theory can illustrate basic concepts in set theory and the theory of discrete structures.

Context-free grammars are used to parse and analyse both artificial languages (for instance programming languages) and natural languages. Turing machines provide a more expressive model of computation. They help computer scientists understand the
limits of mechanical computation by providing a precise definition of the concept of "algorithm".

More detailed contents: Proofs. Finite automata, regular expressions, and related algorithms. Context-free grammars. Properties of regular and context-free languages. A short introduction to Turing machines.

On successful completion of the course the student will be able to:

Knowledge and understanding

• Define different concepts in automata theory and the theory of formal languages, such as (non-) deterministic automaton, regular expression, regular language, context-free grammar, context-free language, and Turing machine.

Competence and skills

• Prove properties of (some) languages, grammars and automata using rigorous mathematical methods.
• Construct finite automata, regular expressions and context-free grammars accepting or generating certain languages.
• Describe the language accepted by a finite automaton or generated by a regular expression or context-free grammar.
• Convert descriptions of regular languages between the following formalisms: deterministic and non-deterministic finite automata as well as regular expressions.
• Simplify automata and context-free grammars.
• Determine if a word belongs to a certain (regular or context-free) language.
• Construct Turing machines for simple tasks.

Judgement and approach

• Manipulate formal descriptions of (some) languages, grammars and automata.

Lectures, exercise sessions.

Language of instruction: English

The course is examined by assignments and an individual written exam given in an examination hall.

If a student who has been failed twice for the same examination element wishes to change examiner before the next examination session, such a request is to be granted unless there are specific reasons to the contrary (Chapter 6 Section 22 HF).

If a student has received a certificate of disability study support from the University of Gothenburg with a recommendation of adapted examination and/or adapted forms of assessment, an examiner may decide, if this is consistent with the course’s intended learning outcomes and provided that no unreasonable resources would be needed, to grant the student adapted examination and/or adapted forms of assessment.

If a course has been discontinued or undergone major changes, the student must be offered at least two examination sessions in addition to ordinary examination sessions. These sessions are to be spread over a period of at least one year but no more than two years after the course has been discontinued/changed. The same applies to placement and internship (VFU) except that this is restricted to only one further examination session.

If a student has been notified that they fulfil the requirements for being a student at Riksidrottsuniversitetet (RIU student), to combine elite sports activities with studies, the examiner is entitled to decide on adaptation of examinations if this is done in accordance with the Local rules regarding RIU students at the University of Gothenburg.

Sub-courses

1. Written hall examination, 4.5 credits
   Grading scale: Pass with distinction (5), Pass with credit (4), Pass (3) and Fail (U)
2. Assignments, 3 credits
   Grading scale: Pass (G) and Fail (U)

The grading scale comprises: Pass with distinction (5), Pass with credit (4), Pass (3) and Fail (U).

In order to get one of the grades 5, 4 or 3 one has to get the grade G on the sub-course Assignments, and a passing grade (5, 4 or 3) on the sub-course Written hall examination. In that case the grade on the course is the grade on the sub-course Written hall examination. In other cases the grade on the course is U (fail).

The course is evaluated through meetings both during and after the course between teachers and student representatives. Further, an anonymous questionnaire is used to ensure written information. The outcome of the evaluations serves to improve the course by indication which parts could be added, improved, changed or removed.

The course is a joint course together with Chalmers.

The course replaces the course DIT322, 7.5 credits. The course cannot be included in a degree which contains DIT322. Neither can the course be included in a degree which is based on another degree in which the course DIT322 is included.