INF248 Theory of Automatic Machine and Artificial Languages

School of Business Administration in Karvina
Winter 2006
Extent and Intensity
2/1/0. 5 credit(s). Type of Completion: z (credit).
Guaranteed by
Department of Informatics and Mathematics – School of Business Administration in Karvina
Course Enrolment Limitations
The course is offered to students of any study field.
Course objectives (in Czech)
Cílem výuky kurzu "Teorie automatů a formálních jazyků? je seznámení studentů se základy teorie formálních a bezkontextových jazyků, ústící v metody syntaktické analýzy.
Syllabus (in Czech)
  • Struktura výkladu:
    1. Jazyky, gramatiky a jejich klasifikace
    2. Konečné automaty
    3. Jazyky typu 3 Chomského klasifikace
    4. Cvičení
    5. Bezkontextové jazyky
    6. Derivační strom, fráze větné formy
    7. Chomského a Greibachové normální formy
    8. Deterministické bezkontextové jazyky
    9. Precedenční jazyky
    10. Kontrolní test z probrané látky + zadání seminární práce;
    11. Zásobníkové automaty
    12. LL jazyky a jejich syntaktická analýza
    13. Výpočet množin FIRST a FOLLOW
    14. Transformace na LL(1) gramatiku
    15. LR gramatiky a jazyky

    Obsah kurzu:
    1. Jazyky, gramatiky a jejich klasifikace
    Jazyk, gramatika, definice, Chomského klasifikace gramatik.
    2. Konečné automaty Pojem konečný automat, definice Turingův stroj.
    3. Jazyky typu 3 Chomského klasifikace
    Regulární množiny a jazyky typu 3, jazyky přijímané konečnými automaty a jazyky typu 3.
    4. Cvičení Konstrukce regulárních gramatik.
    5. Bezkontextové jazyky Definice, pojmy větná forma a fráze větné formy, víceznačnost gramatik.
    6. Derivační strom, fráze větné formy Konstrukce rozkladového derivačního stromu.
    7. Chomského a Greibachové normální formy Definice normální formy, převod do normální formy.
    8. Deterministické bezkontextové jazyky
    Definice, metodu syntaktické analýzy.
    9. Precedenční jazyky Jednoduché precedenční gramatiky, výpočet precedenčních relací.
    10. Kontrolní test z probrané látky + zadání seminární práce;
    11. Zásobníkové automaty Definice, typy a klasifikace, ekvivalence bezkontextových jazyků a jazyků přijímaných zásobníkovými automaty.
    12. LL jazyky a jejich syntaktická analýza
    Základní princip syntaktické analýzy LL jazyků.
    13. Výpočet množin FIRST a FOLLOW Definice množin FIRST, FOLLOW, definice LL(k) gramatiky, LL(1) gramatika jako speciální případ.
    14. Transformace na LL(1) gramatiku Transformace obecné gramatiky na LL(1), procvičení.
    15. LR gramatiky a jazyky Definice LR(k) gramatiky, syntaktické analýza LR jazyků, konstrukce rozkladové tabulky.

    Při přednáškách je využíváno prezentační zařízení a PC. Výuka seminářů probíhá v počítači vybavených učebnách. Studijní materiály jsou dostupné v elektronické podobě prostřednictvímfakultní počítačové sítě.
Language of instruction
Czech
Further comments (probably available only in Czech)
The course can also be completed outside the examination period.
The course is also listed under the following terms Winter 1990, Summer 1991, Winter 1991, Summer 1992, Winter 1992, Summer 1993, Winter 1993, Summer 1994, Winter 1994, Summer 1995, Winter 1995, Summer 1996, Winter 1996, Summer 1997, Winter 1997, Summer 1998, Winter 1998, Summer 1999, Winter 1999, Summer 2000, Winter 2000, Summer 2001, Winter 2001, Summer 2002, Winter 2002, Summer 2003, Winter 2003, Summer 2004, Winter 2004, Summer 2005, Winter 2005, Summer 2006, Summer 2007, Winter 2007, Summer 2008.
  • Enrolment Statistics (Winter 2006, recent)
  • Permalink: https://is.slu.cz/course/opf/winter2006/INF248