Course Formal Languages and Automata Theory

---

Responsible: Prof.Dr.Nissen

Course

Meets requirements of following modules(MID)

• in active programs
  • Ba TIN2012 FSA

Course Organization

Version created 2011-10-14 VID 1 valid from WS 2012/13 valid to

Course identifiers Long name Formal Languages and Automata Theory CID F07_FSA CEID (exam identifier)

Contact hours per week (SWS) Lecture 2 Exercise (unsplit) 2 Exercise (split) Lab Project Seminar Tutorial(voluntary)

Total contact hours Lecture 30 Exercise (unsplit) 30 Exercise (split) Lab Project Seminar Tutorial (voluntary)

Max. capacity Exercise (unsplit) Exercise (split) 40 Lab 18 Project 18 Seminar 40

Total effort (hours): 150

Instruction language

• German

Study Level

• undergraduate

Prerequisites

Textbooks, Recommended Reading

• Hopcraft, Motwani, Ulman: Introduction to Automata Theory, Languages, and Computation, Pearson

Instructors

• Prof.Dr.Nissen

Supporting Scientific Staff

• Dipl.-Ing. Marcel Henk

Transcipt Entry

Formal Languages and Automata Theory

Assessment

Type
wE	written Exam

Total effort [hours]
wE	written Exam

Frequency: 3/year

---

Course components

Lecture/Exercise

Objectives

Lerninhalte (Kenntnisse)

• formal languages and Chomsky hierarchy
• grammars
• abstract machine models
  • finite automata
  • pushdown automata
  • turing machine
• regular expressions
• properties of formal languages
  • closure
  • decidability
  • Pumping Lemma

Acquired Skills

• specify formal languages
• develop grammar fpr given formal language
• develop automata for given formal language
• develop automata for given grammar
• transform specifications
• formal proofs regarding formal languages, grammars and automata

Operational Competences

• formalize real world problems
• develop abstract automata for real problems

Additional Component Assessment

Type
fPS	supervised problem solving

Contribution to course grade
fPS	not rated

Frequency: 1/year