Languages and automata
Fall 2017
- Lectures (by Katalin
Friedl):
- Tu 10-12; T606 on every week,
- Th 10-12; IB147 on even weeks of the semester (these
are 9/14, 10/12, 10/26, 11/9, 11/23, 12/7
- Tests: there will be 3 tests, each
with exercises and some theoretical questions
- To pass a test you need a result of at least 40%
- To pass, you have to pass all the 3 tests
- If you passed the 3 tests then your grade is the average
of the 3 results (from 40% it is 2, from 55% it is 3, from
70% it is 4, from 85% it is 5)
- Office hours: Mo 2pm-4pm or by
appointment
Test #1:
October 12, 6:15pm-7:15pm, where: IB028,
please be there at 6pm.
The results are here.
Repeated test #1 : October
19, 6:15pm-7:15pm in room IB027. It will be similar in style.
The results
are here.
If you failed, there will be a make up test at the end of the
semester. On that you can retake one out of the 3 tests. To use this
opportunity, of course you have to pass the other two tests.
Test #2: November 9,
6:15pm-7:15pm , IB028
The
results are here.
Test 2 solution.
I do not plan to discuss it on class but you can ask about it
outside of class
Repeated Test #2:
Nov 14 (Tuesday!), 6:15pm-7:15pm, IB027
The
result are here.
Test #3: November 30, 6:15pm-7:15pm, IB028
The
results are here.
Test 3
solution.
Unfortunately, I am sick, so there will be no class on Tuesday.
On Thursday there is
no class but I'll be in my office between 11 and 12 if you
want to look at your test. Or you can see it next week.
Until then learn the theorem of Rice, and because of the
cancelled class read about non-deterministic Turing machines and the
NP class.
Repeated Test #3: Dec
13, 10:15am-11:15am, IB025
If you want to take it, please send me an email by Dec 11
The results are here.
(If you have not reached at least 16 points on Test 3
you should come to this.)
For those who failed one test (original and repeated) there is a
last chance to retake it on Dec 18, 12:15-13:15,
IB025
For this, you have to register in the Neptun system.
The results of the tests on Dec 18 are here.
Grades
The actual grades (updated on Dec 13) are
here.
If your grade is 1 (you failed) then register in the Neptun system
for the occasion on Dec 18 and come and retake the failed test.
If your grade is better than 1 (you passed), then you still can come
on Dec 18 to improve your grade, just send me an
email by the evening
of Dec 16, indicating whether you want to
retake Test 1 or 3. Sorry, Test 2 was already good enough for most
of you, there will be no chance to take that again.
In this case your best result (original, repeated or this) for the
given test is counted in your grade.
To study use your (or a classmates') lecture notes or the book
of Michael Sipser:
Introduction to the Theory of Computation
The main topics
covered so far.
Practice problems: 1 Finite
automata, 2
Nondeterministic finite automata, 3 Minimization,
regular expression, 4 Pumping
lemma, 5 Grammars,
6
Grammars/2, 7 Useless symbols,
CF pumping, 8 Pushdown automata,
9
PDA/2, 10 Ambiguosity,
DPDA, 11 Turing machine,
12
Decidable, recognizable,
The tests from last year: 1 2 3 (A
possible solution
for the 3rd one)
For fun
Katalin Friedl, SZIT VIK BME