Az informatika számítástudományi alapjai, 2019/20 őszi félév

A gyakorlatok anyaga:

1. gyakorlat. Ábécék, szavak, nyelvek; műveletek szavakkal és nyelvekkel: halmazműveletek (unió, metszet, különbség, komplementer), konkatenáció, konkatenáció lezárása.
A feladatsor.

2. gyakorlat. Determinisztikus véges automaták, véges automatákkal elfogadott nyelvek.
A feladatsor.

3. gyakorlat. Determinisztikus véges automaták állapotszáma, minimálautomata konstrukciója, pumpálási lemma véges automatával elfogadható nyelvekre.
A feladatsor.

4. gyakorlat. Reguláris kifejezések, nemdeterminisztikus véges automaták; nemdeterminisztikus véges automaták determinisztikussá alakítása.
A feladatsor.

5. gyakorlat. Reguláris kifejezéssel adott nyelvet elfogadó véges automata konstrukciója; véges automatával adott nyelvet leíró reguláris kifejezés konstrukciója.
A feladatsor.

6. gyakorlat. Reguláris grammatikák és véges automaták; környezetfüggetlen grammatikák.
A feladatsor.

7. gyakorlat. Reguláris nyelveket generáló környezetfüggetlen grammatikák, grammatikák egyértelműsége. Törlő szabályok és láncszabályok kiküszöbölése, Chomsky féle normálforma. Szintaktikai elemzés, Cocke-Younger-Kasami algoritmus.
A feladatsor.

8. gyakorlat. Pumpálási lemma környezetfüggetlen nyelvekre. Veremautomaták, adott nyelvet elfogadó veremautomata konstrukciója.
A feladatsor.

9. gyakorlat. Felülről lefelé és alulról felfelé elemző veremautomata konstrukciója adott környezetfüggetlen grammatika alapján.
A feladatsor.

10. gyakorlat. LL(k) grammatikák és nyelvek, az LR(0) elemző.
A feladatsor.