Přeskočit na horní lištu Přeskočit na hlavičku Přeskočit na obsah Přeskočit na patičku

IB102 Automaty a gramatiky

Interaktivní osnova

IB102 Automaty a gramatiky

6. týden: Vztah konečných automatů, regulárních výrazů a gramatik. Rozhodnutelné problémy pro regulární jazyky. Aplikace.

Slajdy k 6. přednášce (22.10.2012)

Domácí úkoly - zadání

DÚ zadání 6. sada, 1. příklad

DÚ zadání 6. sada, 2. příklad

DÚ zadání 6. sada, 1. příklad - .tex

DÚ zadání 6. sada, 2. příklad - .tex

Domácí úkoly - odevzdávárny

Odevzdávárna DÚ: 6. sada, 1.příklad

Odevzdávárna DÚ: 6. sada, 2. příklad

Domácí úkoly - řešení

DÚ řešení 6. sada, 1. příklad

DÚ řešení 6. sada, 2. příklad

Předchozí

IB102 Automaty a gramatiky
- Nyní studovat
  
  Informace o předmětu (sylabus, systém hodnocení,...)
- Nyní studovat
  
  Literatura a jiné informační zdroje
- Nyní studovat
  
  1. týden: Formální jazyky. Gramatiky. Chomského hierarchie.
- Nyní studovat
  
  2. týden: Konečné automaty. Paralelní kompozice automatů.
- Nyní studovat
  
  3. týden: Věta o vkládání. Myhill-Nerodova věta. Aplikace.
- Nyní studovat
  
  4. týden: Minimalizace konečných automatů. Nedeterministické konečné automaty.
- Nyní studovat
  
  5. týden: Automaty s epsilon-kroky. Uzávěrové vlastnosti regulárních jazyků. Regulární výrazy.
- Nyní studovat
  
  6. týden: Vztah konečných automatů, regulárních výrazů a gramatik. Rozhodnutelné problémy pro regulární jazyky. Aplikace.
- Nyní studovat
  
  7. týden: Bezkontextové jazyky. Derivační stromy. Redukované gramatiky.
- Nyní studovat
  
  8. týden: Jednoduchá pravidla a epsilon-pravidla. Chomského normální forma. Věta o vkládání pro bezkontextové jazyky.
- Nyní studovat
  
  9. týden: Přímá a nepřímá levá rekurze. Greibachové normální forma. Zásobníkové automaty.
- Nyní studovat
  
  10. týden: Zásobníkové automaty, metody akceptování. Rozšířené zásobníkové automaty.
- Nyní studovat
  
  11. týden: Zásobníkové automaty a bezkontextové gramatiky. Nedeterministická syntaktická analýza.
- Nyní studovat
  
  12. týden: Algoritmus Cocke-Younger-Kasami. Uzávěrové vlastnosti a (ne)rozhodnutelné problémy pro bezkontextové jazyky.
- Nyní studovat
  
  13. týden: Deterministické bezkontextové jazyky a jejich vlastnosti. Turingovy stroje.

Operace

Prohlédnout vše