UIN1005 Teorie jazyků a automatů I

Filozoficko-přírodovědecká fakulta v Opavě
léto 2012
Rozsah
0/0. 4 kr.
Garance
RNDr. Šárka Vavrečková, Ph.D.
Ústav informatiky – Filozoficko-přírodovědecká fakulta v Opavě
Omezení zápisu do předmětu
Předmět je otevřen studentům libovolného oboru.
Cíle předmětu
V tomto kurzu se zabýváme především teoretickými základy metod požívaných pro modelování struktur a postupů, tedy konečnými automaty, regulárními jazyky, regulárními výrazy a bezkontextovými gramatikami. Na teoretický základ navazují také příklady využití v praxi. Obsahová náplň cvičení vychází a časově sleduje obsahovou náplň přednášek.
Osnova
  • Abeceda, formální jazyky, operace s formálními jazyky.
    Konečný automat.
    Regulární jazyky, Pumping lemma pro regulární jazyky, regulární výrazy, regulární gramatiky.
    Uzávěrové vlastnosti regulárních jazyků.
    Chomského hierarchie jazyků.
    Bezkontextové jazyky, jejich varianty a vlastnosti.
    Normální formy bezkontextových jazyků.
    Pumping lemma pro bezkontextové jazyky.
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 léto 1994, léto 1995, léto 1996, léto 1997, léto 1998, léto 1999, léto 2000, léto 2001, léto 2002, léto 2004, léto 2006, léto 2007, léto 2008, léto 2009, léto 2010, léto 2011, léto 2013.