Andrew Kozlík @

Automaty a konvoluční kódy (cvičení), ZS 2013/14

---

Aktuality

Cvičení 29. 10.

Do příště si rozmyslete tento problém: Nechť k≥1 a L_k je jazyk definovaný regulárním výrazem (0+1)^*1(0+1)^k−1. Dokažte, že každý deterministický konečný automat, který přijímá L_k musí mít alespoň 2^k stavů. Popište, jak sestrojit deterministický konečný automat, který přijímá L_k a má právě 2^k stavů.

Rozvrh

Cvičení se bude konat každé druhé úterý (8. 10., 29. 10., 5. 11., 19. 11., 3. 12. a 17. 12.) od 15:40 do 17:10 v učebně K5.

Podmínky pro udělení zápočtu

1. Aktivita na cvičení.
2. Alespoň 60 % bodů na zápočtové písemce.

Písemka

Termín písemky je stanoven na 17. prosince.

Náhradní písemka se bude konat v pondělí 6. ledna od 13:00 na Katedře algebry.

V písemce se mohou objevit otázky následujících typů:

• Jsou dány dvě posloupnosti, spočítejte jejich konvoluci.
• Jsou dány dva Laurentovy polynomy, spočítejte jejich podíl v tělese formálních Laurentových řad. Výsledek zapište ve tvaru f(x) + g(x)/(1 − x^p), kde f je Laurentův polynom, g je polynom a p je přirozené číslo.
• Je dán jazyk. Rozhodněte, zda je zadaný jazyk regulární. Jestliže je regulární, sestrojte konečný deterministický automat, který jej přijímá. Jestliže není regulární, dokažte to (pomocí pumping lemmatu).
• Je dán regulární výraz, napište jeho negaci.
• Je dán regulární výraz. Sestrojte deterministický konečný automat, který přijímá jazyk definovaný zadaným regulárním výrazem.
• Je dán konečný automat. Napište regulární výraz, který definuje jazyk přijímaný zadaným konečným automatem.
• Je dán nedeterministický konečný automat. Sestrojte deterministický konečný automat, který přijímá tentýž jazyk jako zadaný automat.
• Je dán konvoluční kodér v kontrolorově kanonické formě a vstupní posloupnost, spočítejte výstupní posloupnost.
• Je dán konvoluční kodér v kontrolorově kanonické formě, sestrojte jeho generující matici.
• Je dána generující matice konvolučního kódu.
  • Spočítejte její Smithův rozklad.
  • Spočítejte její pravý inverz.
  • Najděte minimální základní matici, která je s ní ekvivalentní.
  • Rozhodněte, zda je základní.
  • Rozhodněte, zda je katastrofická.
  • Jestliže je katastrofická, uveďte příklad vstupu a výstupu, na kterém se tato vlastnost projevuje.
  • Rozhodněte, zda je minimální.

Odkazy

• Stránka přednášky.
• Stránka k předmětu Automaty a gramatiky.

---