INF248 Teorie automatů a formálních jazyků

Obchodně podnikatelská fakulta v Karviné
zima 2006
Rozsah
2/1/0. 5 kr. Ukončení: z.
Garance
Katedra informatiky a matematiky – Obchodně podnikatelská fakulta v Karviné
Omezení zápisu do předmětu
Předmět je otevřen studentům libovolného oboru.
Cíle předmětu
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.
Osnova
  • 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ě.
Informace učitele
Zisk alespoň 60 bodů ze sta možných:
kontrolní test v 10. týdnu: 0 - 30 b.
seminární práce 0 - 25 b.
závěrečný test 0 - 45 b.
Další komentáře
Předmět je dovoleno ukončit i mimo zkouškové období.
Předmět je zařazen také v obdobích zima 1990, léto 1991, zima 1991, léto 1992, zima 1992, léto 1993, zima 1993, léto 1994, zima 1994, léto 1995, zima 1995, léto 1996, zima 1996, léto 1997, zima 1997, léto 1998, zima 1998, léto 1999, zima 1999, léto 2000, zima 2000, léto 2001, zima 2001, léto 2002, zima 2002, léto 2003, zima 2003, léto 2004, zima 2004, léto 2005, zima 2005, léto 2006, léto 2007, zima 2007, léto 2008.