Address
Jakob-Haringer-Str. 2
5020 Salzburg, Austria
Room 2.17
Phone
+43 (0)662 8044 6417
+43 (0)662 8044 611 (fax)
Skype ana_sokolova
Many thanks to Silviu Craciunas for the photo (RTAS 2010 in Stockholm) and his help with iWeb!
Automata (lectures and instructions), Winter semester 2014/2015
Schedule: Exact dates below, Fridays or Tuesdays blocked (not every week)
First meeting: Friday, October 23 at 10am, FH Salzburg
Language: English
Office hours: Wednesdays 11am-12am
Literature:
-
•Textbook: Introduction to the Theory of Computation, by Michael Sipser, Cengage, 2005.
-
•Textbook: Introduction to Automata Theory, Languages, and Computation by John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Pearson/Addison-Wesley, 2007.
The books can be ordered via Amazon.de .
Prerequisites: None, the course material is self-contained, as are the textbooks. Familiarity with set notation is of course helpful.
Exam: The exam for the lectures is written. In case a student wants to improve his/her grade, an additional oral exam can be scheduled. In order to pass the written exam one needs to have 55% of the maximal points available at the exam. That is, if the exam brings maximally 100 points, in order to pass one needs to have at least 55 points.
Exam date: Friday 18.12.15, 10am - 12:30pm.
Course description: This is a small (1+1) master course for FH students on Automata and Computability. I do not expect theory background and am going to give a somewhat naive (without precise proofs) introduction to automata and the theory of computation. We will introduce different models of computation (in an increasing order of expressivity). In short, we will learn about finite automata, regular languages, context-free grammars, push-down automata, Turing machines, undecidability.
Slides: Whenever slides are used, they will be made available on this webpage. The slides are by no means complete and only serve as help for better presentation. More material is covered during the class (on the board) than visible on the slides.
Schedule (details, e.g. slides and tasks, will be added each week):
-
•Week 1, Friday 23.10.15, Lectures 10am - 11:30am and 11:45am - 1:15pm. Quick Introduction and Finite Automata. In particular, DFA, regular languages and regular expressions, Kleene theorem, NFA (just the definition and some examples).
We looked at many examples on the board and proved some closure properties of regular languages (needed for the theorem of Kleene). You may read p.31-54 (Chapter 1) in the Sipser book and look at additional exercises at the end of Chapter 1. Here you can download the slides and the homework for our next meeting. -
•Week 2, Tuesday 3.11.15, Lectures 1:30pm - 3pm, Instructions 3:15pm - 4:45pm. NFA in detail, equivalence of NFA and DFA, examples, closure properties. Nonregular languages remain for next time. You may read p.55-77 (Chapter 1) in the Sipser book and look at additional exercises at the end of Chapter 1. Here you can download the slides and the homework for our next meeting.
-
•Week 3, Tuesday 17.11.15, Lectures 10am - 11:30am, Instructions 11:45am - 1:15pm. Nonregular languages, context-free grammars and context-free languages, properties of such, non-context-free languages. You may read Section 1.4 and Section 2.1. in the Sipser book and look at additional exercises at the end of the chapters. Here you can download the slides and the homework for our next meeting.
-
•Week 4, Tuesday 24.11.15, Lectues 1:30pm - 3pm, Instructions 3:15pm - 4:45pm. Push-down automata and deterministic push-down automata. You may read Section 2.2. in the Sipser book (p. 109-123) and look at the exercises at the end of Chapter 2. Here you can download the slides and the homework for our next meeting.
-
•Week 5, Tuesday 1.12.15, Lectues 1:30pm - 3pm, Instructions 3:15pm - 4:45pm. Turing machines, basics and examples. You may read Chapter 3 from the Sipser book (p. 135-165) and look at the exercises at the end of the chapter. Here you can download the slides and the homework for our next meeting. Here is a set of example exam tasks, for your information. You need not deliver these tasks, we will discuss and solve them at our next meeting.
-
•Week 6, Friday 11.12.15, Lecture 10am - 10:45am, Instructions 10:45am - 1:15pm (with 15min break). Undecidability and preparing for the exam.
-
•Week 7, Friday 18.12.15, Exam 10am - 12:30pm.
Once I found the following quote (source no longer known, it was part of some ETH course on theory in computer science). I find it contains perfect arguments.
Why a theory of computation? Nothing is more practical than a good theory!
-
•What kind of knowledge can you acquire today that will serve you for your entire career, that will still be valid in the year 2050?
(Hint: concepts that have already survived half a century of CS development.) -
•Theory extracts the basic concepts that apply to any conceivable implementation of computing machines. These concepts are of timeless validity, in contrast to technology-specific and product-specific know-how.
-
•A firm mastery of basic concepts is a great “data compression technique”: many seemingly unrelated facts, presented in time-varying jargon, can be understood intuitively as instances of the same principle.
(end of quote)
Grading rules: Presence in class is obligatory. Each student can miss one class, but not more than that without a serious reason.
The total grade is determined by (1) the exam grade (80% contribution to the total grade) and (2) homework and activity in class (20% contribution to the total grade).
Each week after the class (Friday or Tuesday evening) the students are given a set of several homework exercises that are to be solved in groups of at most three people, signed, and delivered before the following class. These exercises are to be discussed in the following class. I will correct one randomly chosen exercise per week and the students will get a grade for that one. The corrected homework will be returned to the students with grades. Needless to say, copying between different groups is unacceptable and will be sanctioned.
During class I will present the solution of the chosen corrected exercise and the students will be asked to present the solutions/discuss the other exercises. I may also present additional solutions.
Ana Sokolova
Dr. TU Eindhoven, The Netherlands, 2005
Associate Professor
Department of Computer Sciences
Austria
