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: Tuesdays 10:45am - 12:15pm (lectures)
Tuesdays 12:30pm - 2:00 pm (instructions)
Every “second” Tuesday, exact dates below.
First meeting: Tuesday, October 21 at 10:45, Seminarroom 358, 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: Tuesday 27.1.15, 10:45am - 12:15pm.
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, Tuesday 21.10.14, Lectures 10:45am - 12:15pm, Instructions 12:30pm - 2pm. 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 4.11.14, Lectures 10:45am - 12:15pm, Instructions 12:30pm - 2pm. 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. The homework is to be delivered by Friday 14.11.14 at noon.
-
•Week 3, Tuesday 18.11.14, Lectures 10:45am - 12:15pm, Instructions 12:30pm - 2pm. Nonregular languages, context-free grammars and context-free languages, properties of such, non-context-free languages. You may read Chapter 2 except 2.2. in the Sipser book (p. 99-109 and p.123-134) and look at the exercises at the end of Chapter 2. Here you can download the slides and the homework for our next meeting. The homework is to be delivered by Friday 28.11.14 at noon.
-
•Week 4, Tuesday 2.12.14, Lectues 10:45am - 12:15pm, Instructions 12:30pm - 2pm. 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. The homework is to be delivered by 16.12.14 before the class --- you can bring it in class as I will not be able to correct it in advance.
-
•Week 5, Tuesday 16.12.14, Lectues 10:45am - 12:15pm, Instructions 12:30pm - 2pm. 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. The homework is to be delivered by Friday 10.1.15 at noon. 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, Tuesday 13.1.15, Lecture 10:45am - 11:30am, Instructions 11:45am - 2:15pm (with 15min break). Undecidability and preparing for the exam. We discussed the notion of an algorithm, and the relationship between Turing-decidable, Turing-recognizable, and Turing-nonrecognizable languages. We showed that some problems (languages) are undecidable. This rounds up the material for the course. In the excercise session we solved the homework tasks on Turing machines and also the tasks given in the example exam above.
-
•Week 7, Tuesday 27.1.15, Exam 10:45am - 13:15pm.
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 (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
