Automata and Convolutional Codes (tutorial), Fall 2014
Schedule
The tutorial will usually take place every other Friday (October 10th, October 24th, November 7th, November 21st, December 5th and December 19th) from 12:20 to 13:50 in room K7.
The tutorial on November 21st is cancelled because the Fall School of the Department of Algebra takes place on that day. We will instead have a tutorial on November 28th from 14:00 to 15:30 in room K7.
Earning credit
To earn credit you have to:
- work out at least one problem on the blackboard in class and
- obtain at least 60 % on the test.
The test
The test will take place on December 19th.
The following types of questions may appear on the test:
- Given a language, determine whether it is regular. If it is regular, then construct a deterministic finite automaton which accepts the language. If it is not regular, then prove it using the pumping lemma.
- Given a regular expression, construct a deterministic finite automaton which accepts the language defined by the regular expression.
- Given a finite automaton, find the regular expression which defines the language accepted by the automaton.
- Given a non-deterministic finite automaton, construct a deterministc finite automaton which accepts the same language.
- Given a convolutional encoder in controler normal form and an input sequence, compute the output sequence.
- Given a convolutional encoder in controler normal form, construct its generating matrix.
- Given a generating matrix of a convolutional code,
- compute its Smith decomposition;
- compute its right inverse;
- find an equivalent minimal basic matrix;
- determine whether it is basic;
- determine whether it is catastrophic;
- if it is catastrophic, then give an example of an input vector and an output vector proving this;
- determine whether it is minimal.
Písemka
Termín písemky je stanoven na 19. prosince.
V písemce se mohou objevit otázky následujících typů:
- 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. 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í.
Links