Tematika (címszavakban)

2017 ősz

   Az első zh anyaga lilával látható, a második zh anyaga meg zölddel, a harmadik zh anyaga pirossal.

  1. (szept. 6. szerda): Definíciók (ábécé, szó, nyelv), véges automata, példák véges automatákra, reguláris nyelv, reguláris nyelvek zártak az unióra, metszetre, különbségre és komplementerre
  2. (szept. 13.): Hiányos véges automata, nemdeterminisztikus véges automata, epszilon-átmenetes véges automata, ezekből hogyan lehet determinisztikus, teljesen specifikált véges automatát csinálni; két reguláris nyelv konkatenáltja reguláris
  3. (szept. 14): Reguláris nyelv tranzitív lezártja reguláris; Minimálautomata
  4. (szeptember 21): Sportnap miatt elmaradt
  5. (szeptember 28.): Pumplási lemma reguláris nyelvekre, Reguláris kifejezések, regkifből VA
  6. (október 4.): VA-ból regkif, A Python és a természetes nyelvek nyelvtanai, Chomsky elmélete, Nyelvtanok: definíció, példák, Chomsky-hierarchia
  7. (október 11.) Nyelvtan, reguláris és CF nyelvtanok, Reguláris nyelvtanok és VA-k egyenértékűsége, eldöntési kérdések reguláris nyelvekről. CF nyelvtanok átalakításai: epszilon-mentesítés, láncszabályok kiküszöbölése;
  8. (október 12.) CF pumpálás, CF nyelvek zártsági tulajdonságai, Veremautomata: definíció
  9. (október 18.) Veremautomata működése, példa; Cf nyelvtanok és veremautomaták egyenértékűsége; determinisztikus veremautomata
  10. (október 25.) determinisztikus PDA, det CF nyelvek, detCF nem egyenlő CF és hogy ez miért nem nagy baj, CYK algoritmus a fák megkeresésével is  (kiegészítés a jegyzethez)
  11. (október 26.) CF nyelvtanok és nyelvek egyértelműsége, az egyértelműség és a det CF kapcsolata; Turing gép: definíció, működés, példa
  12. (november 1.) Munkaszüneti nap miatt elmaradt
  13. (november 8.) 1-szalagos, determinisztikus TG a palindrómák nyelvére, R és RE nyelvosztály definíciója, kapcsolatuk, van nem RE-beli nyelv; k-szalagos determinisztikus TG definíciója, példa: 2-szalagos gép a palindrómákra, k-szalagos mindig szimulálható 1-szalagossal;
  14. (november 9.) Nemdeterminisztikus TG, szimulálása determinisztikussal; Kiszámolós TG, példa,  Church-Turing tézis; 
  15. (november 15.) Turing-gépek kódolása, algoritmussal eldönthető, hogy egy szó TG kód-e, Diagonális nyelv nem RE-beli, Univerzális TG, univerzális nyelv és megállási nyelv RE-ben van, de nem R-beli; R és RE zártsági tulajdonságai: metszetre és unióra igen, komplementerre R zárt