Languages and automata

Fall 2017

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.


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