KIV / TI - Teoretická informatika
Zadání semestrálních prací

Následující informace jsou určeny studentům, kteří navštěvují cvičení P. Lobaze. Studenti jiných cvičení se řídí pokyny svých cvičících.

Forma semestrální práce

Zadání semestrálních prací

Níže uvedený seznam obsahuje náměty. Po domluvě je možné zadání všelijak ohýbat, slučovat, rozdělovat apod. Přijdete-li se svým zadáním souvisejícím s teoretickou informatikou (automaty, gramatiky, regulární výrazy, kódování, formální logika), také se domluvíme.

Aplikace konečných automatů

  1. Řízení světelné křižovatky (s případným vyhodnocením efektivity)
  2. Řízení výtahu (s případným vyhodnocením efektivity)
  3. Řízení prodejního automatu
  4. Řízení digitálních hodinek
  5. Řízení nějakého jiného rozumně složitého zařízení (pračka, termostat, ...)
  6. Lexikální analyzátor

Zpracování konečných automatů

  1. Převod NKA na DKA
  2. Kompozice několika DKA
  3. Minimalizace počtu stavů DKA
  4. Převod DKA na regulární výraz

Kódování

  1. Huffmanovo kódování
  2. Adaptivní Huffmanovo kódování
  3. Aritmetické kódování
  4. Hammingovo kódování
  5. Golayovo kódování
  6. Cyklické kódování

Pomůcky pro výuku TI

  1. Vizualizace činnosti rozpoznávacího konečného automatu
  2. Vizualizace činnosti konečného automatu s výstupní funkcí
  3. Vizualizace činnosti sítě konečných automatů s výstupními funkcemí
  4. Vizualizace činnosti nedeterministického konečného automatu
  5. Hledání řetězců generovaných gramatikou
  6. Vizualizace odvozování řetězců generovaných gramatikou
  7. Vizualizace principu Huffmanova kódování
  8. Vizualizace libovolného jiného postupu z předmětu TI

Podrobnosti k zadání

Řízení světelné křižovatky (s případným vyhodnocením efektivity)

Vytvořte konečný automat (resp. síť konečných automatů) pro řízení stavu semaforů na rozumně složité křižovatce; můžete si vybrat nějakou reálnou křižovatku. Řídicí automat musí reagovat na zvolený typ externího vstupu (tlačítko pro chodce nebo tramvaje, sledování dopravy apod.). Vytvořte program, který činnost automatu vizualizuje a umožňuje sledovat reakci na externí vstupy.

Při řešení reakce na externí vstup použijte jiný přístup než prosté zrychlení cyklu, které jsme si ukazovali na prvním cvičení.

Zadání lze rozšířit a tím povýšit na mnohem užitečnější aplikaci: vytvořte navíc simulátor, který bude náhodně generovat příjezdy automobilů a příchody chodců a který bude sledovat jejich pohyb na základě stavu semaforů. Výsledkem činnosti simulátoru je zejména statistika odhadující průměrnou dobu čekání na zelenou (pro chodce i pro automobily), propustnost křižovatky apod. Můžete se také pokusit nalézt parametry řídicího automatu (zejména čekacích dob), které povedou k co nejlepší statistice. Rozhodnete-li se pro rozšíření zadání o simulaci křižovatky, je možné (a vhodné) řešit semestrálku v trojici.

Je-li řešení doplněno o simulátor s vyhodnocením průjezdnosti, lze zadání dále rozšířit: například lze vymyslet několik alternativních řídicích automatů a simulací vyhodnotit, který z nich se chová lépe. Alternativním přístupem k řízení je například logika chování automatu po stisku chodeckého tlačítka: automat může buď dočasně zrychlit cyklus, nebo co nejrychleji přejít do požadované stavu s dodatkem, že úmyslným mačkáním chodeckých tlačítek nelze křižovatku zablokovat. Rozhodnete-li se i pro toto rozšiření zadání, je možné (a vhodné) řešit semestrálku ve čtveřici.

Hlavním smyslem zadání je vyzkoušet si návrh implementace pomocí konečného automatu. Implementace proto musí striktně dodržovat princip konečněautomatového návrhu; jiné implementace budou vráceny k přepracování.

Při implementaci začněte od konečného automatu, případné uživatelské rozhraní je doplněk, který doděláte nakonec. Rozhodně se nesnažte automat simulovat nástroji, které vám poskytuje knihovna pro tvorbu GUI, např. JavaFX apod.!

Řízení výtahu (s případným vyhodnocením efektivity)

Vytvořte konečný automat (resp. síť konečných automatů) pro řízení nejrůznějších zařízení nutných k činnosti výtahu. Automat tedy bude zapínat a vypínat motory (motor výtahu, otvirání dveří apod.) a světla (výtah jede, indikace zvoleného podlaží apod.), reagovat bude jak na vstupy externí (přivolání výtahu, volba podlaží, zastavení/opětovné rozjetí výtahu apod.), tak na vstupy interní (indikátor polohy výtahu, indikátor otevření/zavření dveří, bezpečnostní čidlo na dveřích apod.). Výtah by měl být pro alespoň čtyřpodlažní budovu.

Dále vytvořte program, který činnost výtahu vizualizuje a umožňuje manipulovat s externími i interními vstupy (např. simulovat poškození bezpečnostního čidla).

Zadání lze rozšířit a tím povýšit na mnohem užitečnější aplikaci: vytvořte navíc simulátor, který bude náhodně generovat příchody lidí a jejich povely pro výtah. Výsledkem činnosti simulátoru je zejména statistika odhadující průměrnou dobu čekání na výtah, průměrně ušetřený čas oproti chůzi po schodišti apod. Rozhodnete-li se pro rozšiření zadání o simulaci výtahu, je možné (a vhodné) řešit semestrálku v trojici.

Je-li řešení doplněno o simulátor s vyhodnocením čekání, lze zadání dále rozšířit: například lze vymyslet několik alternativních řídicích automatů a simulací vyhodnotit, který z nich se chová lépe. Příklad alternativních přístupů k řízení je například logika chování automatu po stisku přivolávacího tlačítka: automat může buď přivolávací tlačítko během jízdy výtahu ignorovat, nebo se může snažit o průbežné zastavování v patrech. Rozhodnete-li se i pro toto rozšíření zadání, je možné (a vhodné) řešit semestrálku ve čtveřici.

Hlavním smyslem zadání je vyzkoušet si návrh implementace pomocí konečného automatu. Implementace proto musí striktně dodržovat princip konečněautomatového návrhu; jiné implementace budou vráceny k přepracování.

Při implementaci začněte od konečného automatu, případné uživatelské rozhraní je doplněk, který doděláte nakonec. Rozhodně se nesnažte automat simulovat nástroji, které vám poskytuje knihovna pro tvorbu GUI, např. JavaFX apod.!

Řízení prodejního automatu

Vytvote konečný automat (resp. síť konečných automatů) pro řízení zvoleného prodejního automatu (nápojového, na jízdenky apod.).

Automat bude mít tři typy vstupů: stisky tlačítek, indikaci hodnoty vhozené mince a signály z různých čidel (např. "došla káva", "došly kelímky" aj.). Svými výstupy bude automat řídit motory, elektromagnety apod., které zajistí vracení mincí z mincovníku, přípravu kelímku, zapnutí/vypnutí ohřívání vody, puštění/zavření přívodu vody apod. Konkrétní vnitřní prvky automatu si realisticky navrhněte sami.

Vytvořte dále aplikaci, která vhodným způsobem automat vizualizuje a umožňuje simulovat mačkání tlačítek, vhazování mincí a sledování vrácení přeplatku; rovněž by měla umožnit simulovat výjimečné stavy, např. "neteče voda" apod.

Hlavním smyslem zadání je vyzkoušet si návrh implementace pomocí konečného automatu. Implementace proto musí striktně dodržovat princip konečněautomatového návrhu; jiné implementace budou vráceny k přepracování.

Při implementaci začněte od konečného automatu, případné uživatelské rozhraní je doplněk, který doděláte nakonec. Rozhodně se nesnažte automat simulovat nástroji, které vám poskytuje knihovna pro tvorbu GUI, např. JavaFX apod.!

Řízení digitálních hodinek

Vytvořte konečný automat (resp. síť konečných automatů) pro řízení digitálních hodinek se stopkami.

Automat bude mít jeden vstup interní (od časovače, který generuje pulsy s periodou např. 1/100 s) a několik vstupů externích (tlačítko 1 stisknuto, tlačítko 1 uvolněno, ...). Pomocí externích vstupů musí jít nastavit přesný čas a spustit hodiny, přepnout se do režimu stopek, spustit a pozastavit je a přejít zpět do režimu zobrazení hodin. Automat generuje výstup pro řízení displeje: obsahuje tři dvojice cifer oddělených "dvojtečkami", každá cifra je zobrazována klasickým sedmisegmentovým polem. Automat tedy musí mít nejméně 7 × 2 × 3 = 42 výstupů.

Externí vstupy (tlačítka) navrhněte sami. Nezapomeňte, že každý mechanický prvek prodražuje výrobu a činí zařízení poruchovějším. Také uvažte, že ovládání by mělo být co nejjednodušší.

Vytvořte dále aplikaci, která vhodným způsobem hodinky vizualizuje a umožňuje simulovat mačkání tlačítek.

Hlavním smyslem zadání je vyzkoušet si návrh implementace pomocí konečného automatu. Implementace proto musí striktně dodržovat princip konečněautomatového návrhu; jiné implementace budou vráceny k přepracování.

Při implementaci začněte od konečného automatu, případné uživatelské rozhraní je doplněk, který doděláte nakonec. Rozhodně se nesnažte automat simulovat nástroji, které vám poskytuje knihovna pro tvorbu GUI, např. JavaFX apod.!

Řízení nějakého jiného rozumně složitého zařízení (pračka, termostat, ...)

Obdobně jako v předchozích zadáních: vytvořit řídicí logiku konečným automatem, naprogramovat ji a vytvořit vhodnou vizualizaci.

Lexikální analyzátor

Vytvotřte pomůcku, která analyzuje textový vstup (pro jednoduchost řetězec) a indikuje nalezené klíčové slovo. Zadání se nejlépe popíše příkladem, byť trochu umělým.

Dejme tomu, že dálkově ovládáme jakési zařízení, například semafory na křižovatce. Aby se nám komunikační jazyk lépe pamatoval, řídíme zařízení dohodnutými klíčovými slovy, například

rovneVpravoProSeverJih
dolevaProSeverJih
rovneVpravoProVychodZapad
dolevaProVychodZapad
oranzovaProVsechny
cervenaProVsechny

a tak dále. Zařízení by přijalo řetězec na vstupu, rozpoznalo by jej a provedlo příslušnou akci. Kód by mohl vypadat například takto:

command = getStringFromInput();
if (command.equals("rovneVpravoProSeverJih")) { ... }
else if (command.equals("dolevaProSeverJih")) { ... }
else if (command.equals("rovneVpravoProVychodZapad")) { ... }
...
else { /* syntax error */ ... }

Kód by zajisté fungoval, ale poměrně pomalu: uvědomme si, že pro jedno porovnání řetězců je nutné porovnat v nejhorším případě všechny jejich znaky. Pokud tedy zadáme řídicí příkaz, který je v naší implementaci posloupností porovnávacích příkazů až na konci, je nutné napřed provést všechna předchozí porovnání, což dohromady činí spoustu porovnávání jednotlivých znaků. Pokud omylem zadáme řídicí příkaz "rrrovneVpravoProSeverJih", je nutné provést všechna porovnání, i když ze seznamu řídicích příkazů je celkem hned zřejmé, že jde o syntaktickou chybu.

Mnohem výhodnější je zřejmě sestrojit klasifikační konečný automat akceptující písmena; na konci řetězce se pak stačí podívat, v jakém stavu automat skončil. Takové řešení je mimořádně výhodné, je-li možných řídicích příkazů hodně (desítky a více) a rozpoznávat je potřebujeme co nejrychleji. Sestrojit klasifikační automat je sice myšlenkově jednoduché, ale pracné.

Proto by bylo příjemné, kdybychom měli jakousi funkci identifyString(), která by vstupní řetězec identifikovala, a tuto funkci za nás někdo na objednávku napsal. Objednávka by mohla vypadat například takto:

1 rovneVpravoProSeverJih
2 dolevaProSeverJih
3 rovneVpravoProVychodZapad
4 dolevaProVychodZapad
5 oranzovaProVsechny
6 cervenaProVsechny

Každý řádek obsahuje jak samotný řídicí příkaz, tak jeho jednoduchý číselný identifikátor. Ideální bude, když "funkci na objednávku" napíše pomocný program. Jeho vstupem bude textový soubor s výše uvedenou strukturou, tj.

vystupniHodnota1  retezec1
vystupniHodnota2  retezec2
...
vystupniHodnotaN  retezecN

a výstupem bude soubor se zdojovým textem funkce ve zvoleném programovacím jazyce; např. v ANSI C by to byl soubor identifyString.c obsahující kód funkce


int identifyString(char *string) {
 ...
}

vracející hodnotu 0 v případě syntaktické chyby a hodnotu z "objednávky" v případě identifikovaného řetězce.

Zadání je zárodkem tzv. lexikálního analyzátoru. Standardní lexikální analyzátory rozpoznávají na vstupu podle "objednávky" nejenom klíčová slova (v předchozí terminologii "řidicí příkazy"), ale i čísla, speciální řetězce (např. datum, rodné číslo, e-mailová adresa atd.). Zájemci se mohou pokusit v tomto smyslu o rozšíření zadání; struktura "objednávky" pak bude o něco složitější a o něco (ne o moc!) bude složitejší i implementace.

Převod NKA na DKA.

Vytvořte program, který načte textový soubor s definicí nedeterministického konečného automatu, převede jej na ekvivalentní deterministický konečnný automat a jeho definici zapíše do výstupního souboru. Program se bude volat z příkazové řádky například takto:

prevodNKAnaDKA vstup.TI2 vystup.TI2

Pro ověření funkčnosti napište rovněž program, který načte ze vstupního souboru definici deterministického konečného automatu a ověří na vstupním řetězci činnost automatu. Program se bude volat z příkazové řádky například takto:

spustDKA automat.TI2 12111212232

Formát souboru s definicí automatu viz hlavní stránka předmětu.

Kompozice několika DKA.

Vytvořte program, který načte několik textových souborů s definicemi deterministických konečných automatů, vytvoří jejich zadanou kompozici (AND nebo OR) a výsledný deterministický konečný automat zapíše do výstupního souboru. Program se bude volat z příkazové řádky například takto:

kompoziceDKA prunik.TI2 AND automat1.TI2 automat2.TI2 automat3.TI2

Uvedený příklad tedy vytvoří konečný automat prunik.TI2 akceptující řetězce z průniku jazyků definovaných automaty automat1.TI2 až automat3.TI2. Pro ověření funkčnosti napište rovněž program, který načte ze vstupního souboru definici deterministického konečného automatu a ověří na vstupním řetězci činnost automatu. Program se bude volat z příkazové řádky například takto:

spustDKA prunik.TI2 12111212232

Formát souboru s definicí automatu viz hlavní stránka předmětu.

Minimalizace počtu stavů DKA.

Vytvořte program, který načte textový soubor s definicí deterministického konečného automatu, převede jej na ekvivalentní deterministický konečný automat s minimálním počtem stavů a jeho definici zapíše do výstupního souboru. Program se bude volat z příkazové řádky například takto:

minimalizaceDKA vstup.TI2 vystup.TI2

Pro ověření funkčnosti napište rovněž program, který načte ze vstupního souboru definici deterministického konečného automatu a ověří na vstupním řetězci činnost automatu. Program se bude volat z příkazové řádky například takto:

spustDKA automat.TI2 12111212232

Formát souboru s definicí automatu viz hlavní stránka předmětu.

Převod DKA na regulární výraz.

Vytvořte program, který načte textový soubor s definicí deterministického konečného automatu a vytvoří regulární výraz popisující jazyk akceptovaný automatem. Program se bude volat z příkazové řádky například takto:

prevodDKAnaRV vstup.TI2

Například pro konečný automat

DKAR#  //  Typ souboru
3 //  Počet prvků množiny stavů, stavy jsou pak implicitně S1,S2,S3
2 //  Počet prvků množiny vstupů, vstupy jsou pak implicitně  1, 2
// Přechodová tabulka bude mít 3 řádky, v každém budou 2 stavy oddělené mezerami
S1# S1 S2
S2# S3 S3
S3# S3 S3
S1     // Počáteční stav
1   S2 //  Počet koncových stavů a koncové stavy

může výstupní regulární výraz vypadat takto:

1*2

(tj. automat akceptuje slova s libovolným početem jedniček na začátku a ukončená právě jednou dvojkou)

Významné plus řešitelé získají, bude-li program generovat výstupní regulární výraz ve formátu regexp kompatibilním např. s Javou. Program pak bude moci vygenerovat podobný zdrojový kód, kterým se činnost regulárního výrazu snadno otestuje:

import java.util.regex.Pattern;
import java.util.regex.Matcher;
public class RegexTest {
    public static void main(String[] args){
        Pattern pattern = Pattern.compile("1*2");
        Matcher matcher = pattern.matcher(args[1]);

        boolean found = false;
        while (matcher.find()) {
            System.out.format("Found" +
                " \"%s\" starting at " +
                "index %d and ending at index %d.%n",
                matcher.group(),
                matcher.start(),
                matcher.end());
            found = true;
        }
        if(!found){
            System.out.format("No match found.%n");
        }
    }
}

(Struktura generovaného programu je pevná, mění se pouze regulární výraz na řádce 5)

Huffmanovo kódování

Vytvořte jednoduchý kompresní a dekompresní program. Jeho vstupem bude obecný (binární) soubor, výstupem soubor komprimovaný Huffmanovým kódováním. Výstupní soubor v sobě musí obsahovat všechny potřebné informace pro dekompresi, tj. zejména četnosti vstupních znaků. Pro jednoduchost předpokládejte, že vstupní soubor bude dlouhý maximálně 2 GiB.

Program se bude volat z příkazové řádky, např. pro kompresi

huffman -c input.txt compressed.huf

nebo pro dekompresi

huffman -d compressed.huf decompressed.huf

Po kompresi nechť program vypíše statistiku: jaká byla velikost vstupního souboru, jaká je velikost výstupního kódu (bez četností a dalších informací nutných k dekompresi), jaká je velikost pomocných informací, jaký je dosažený kompresní poměr.

Kvůli sobě (i kvůli mně) do programů zabudujte přepínač "-v". Pak bude program čitelným způsobem hlásit, co dělá či udělal. Například po spuštění

huffman -v -c input.txt compressed.huf

by program mohl hexadecimálně vypsat vstup (předpokládá se, že krátký), vypsat tabulku četností, kódovací tabulku (vstupní symbol ⇒ binární kód) a nějakým srozumitelným způsobem generovaný výstup. Obdobně by informace užitečné pro kontrolu činnosti program vypisoval při dekompresi.

Zájemci, kteří si chtějí se zadáním pohrát, mají nejméně dvě možnosti. První je vymyslet efektivní uložení dodatečných informací nutných k dekompresi, neboť ty budou hrát u krátkých souborů významnou roli. Druhá je vyzkoušet, jaký vliv má volba vstupní abecedy na kompresní poměr; první volba asi padne na osmice bitů (tj. vstupní abeceda má 256 symbolů). Jak se chování kompresoru změní, bude-li například vstupním symbolem čtveřice bitů (půlbyte, tj. vstupní abeceda má 16 symbolů) nebo šestnáctice bitů (dva byte, tj. vstupní abeceda má 65536 symbolů)? Alternativně je možné zpracovat zadání "Adaptivní Huffmanovo kódování".

Po zkušenostech z minulých let pro jistotu opakuji: vstupem programu má být binární soubor, tj. soubor s libovolným obsahem. Neomezujte se na textové či jiné speciální soubory! Požadavku přizpůsobte jak příkazy čtení/zápisu souboru, tak tvar kontrolních hlášení programu.

Adaptivní Huffmannovo kódování

Zadání je v podstatě stejné jako "Huffmanovo kódování". Rozdílem je kompresní algoritmus: zatímco Huffmanovo kódování vyžaduje dva průchody vstupem (první pro zjištění četností, druhý pro kódování), adaptivní Huffmanovo kódování četnosti na začátku nějak odhadne a během kódování je upřesňuje, k činnosti tedy stačí jeden průchod. Dekompresor na začátku činnosti ví, jak kompresor četnosti odhadl (protože jsou domluveni), a po dekompresi každého znaku tabulku četností upraví stejně jako kompresor; komprimovaný soubor tedy v sobě nemusí nést dodatečné informace. Pokud se navíc struktura vstupu mění, může se adaptivní kódování proměnlivé struktuře přizpůsobovat, např. brát potaz pouze četnosti v posledních 1000 symbolech.

Implementujte buď nějaký známý algoritmus adaptivního Huffmanova kódování, nebo se pokuste navrhnout svůj. V nejlepším případě se implementuje několik algoritmů a ty se mezi sebou porovnají; pak je ale vhodné pracovat ve trojici nebo více lidech.

Aritmetické kódování

Zadání je v podstatě stejné jako "Huffmanovo kódování". Rozdílem je kompresní algoritmus. Toto zadání doporučuji lidem s mimořádným zájmem o algoritmizaci. Nepokoušejte se vymyslet algoritmus sami, doporučím vám nějaké studijní materiály s praktickými radami.

Hammingovo kódování

Vytvořte program pro kódování/dekódování vstupního binárního souboru Hammingovým kódem (n, k). Program se bude volat z příkazové řádky, např. pro kódování kódem (7, 4)

hamming -c 7 4 input.txt coded.ham

a pro dekódování

hamming -d 7 4 coded.ham decoded.txt

Předpokládejte, že uživatel zadává parametry správně, tj. že parametry (n,k) kódu zadá pro kódování i dekódování stejné.

Pro testování robustnosti vytvořte navíc přepínač "-de" obsahující navíc pravděpodobnost přenosové chyby. Například příkaz

hamming -de 100 7 4 coded.ham decoded.txt

napřed vstup "zašumí", přičemž průměrná četnost chyby bude 1 chyba na 100 bitů, neboli pravděpodobnost chybného přenosu bitu je 0,01. V tomto režimu program vypíše statistiku s počtem opravených symbolů, detekovaných neopravených symbolů a nedetekovaných chybných symbolů.

Kvůli sobě (i kvůli mně) do programů zabudujte přepínač "-v". Pak bude program čitelným způsobem hlásit, co dělá či udělal. Například příkaz

hamming -v -c 7 4 input.txt coded.ham

vypíše generující a kontrolní matice a rozumným způsobem dá vědět, jak vstup kóduje na výstup. Obdobně příkaz

hamming -de 100 7 4 coded.ham decoded.txt

by měl vypsat generující a kontrolní matice a rozumným způsobem hlásit, jaké vstupní bity načítá, kde dochází k poškození a jak se načtený vstupní symbol dekóduje.

Golayovo kódování

Zadání je v podstatě stejné jako "Hammingovo kódování". Rozdílem je kódovací algoritmus: tentokát jde o Golayúv kód (23,12) nebo (24,12).

Cyklické kódování

Zadání je v podstatě stejné jako "Hammingovo kódování". Rozdílem je kódovací algoritmus: tentokát jde o cyklický kód (n, k) se zadaným generujícím polynomem.

Vizualizace činnosti rozpoznávacího konečného automatu

Vytvořte program, který přehledným způsobem a vhodnou grafikou umožní sledovat činnost pevně zadaného konečného automatu. Uživatel bude mít možnost zadat vstupní řetězec a krokovat průchod automatu jeho stavy; současně uvidí, jaký znak ze vstupu se právě zpracovává. Vizualizace také jasně signalizuje, zda je doposud zpracovaná část řetězce automatem akceptována.

Program musí být navržen tak, aby uměl simulovat činnost libovolného rozpoznávacího konečného automatu. "Pevné zadání" v předchozím odstavci je míněno jen jako usnadnění s grafickou částí programu: nebudete muset řešit, jak nakreslit stavy a hrany přehledně a bez křížení.

Vizualizace činnosti konečného automatu s výstupní funkcí

Zadání je v podstatě stejné jako "Vizualizace činnosti rozpoznávacího konečného automatu". V tomto případě program navíc indikuje doposud vygenerovaný výstup.

Vizualizace činnosti sítě konečných automatů s výstupními funkcemí

Zadání je v podstatě stejné jako "Vizualizace činnosti rozpoznávacího konečného automatu". V tomto případě program navíc indikuje doposud vygenerovaný výstup.

Vizualizace činnosti nedeterministického konečného automatu

Zadání je v podstatě stejné jako "Vizualizace činnosti rozpoznávacího konečného automatu". V tomto případě program ukazuje, že se automat nachází v některém z několika stavů; je-li jeden ze stavů koncový, signalizuje program, že doposud zpracovaný řetězec je nedeterministickým konečným automatem akceptován.

Hledání řetězců generovaných gramatikou

Vytvořte program, který načte ze vstupního souboru gramatiku typu 2 a vypíše všechny řetězce délky maximálně N terminálních symbolů, které gramatika generuje. Program se může volat z příkazové řádky například takto

genString gramatika.TI 5

Pokud bude vstupní gramatika dána jako

G2  //  Typ souboru
3   //  Počet prvků množiny neterminálních symbolů, neterminály jsou pak implicitně A,B,C
2   //  Počet prvků množiny terminálních symbolů, výstupy jsou pak implicitně a, b 
    //  prázdný řetězec budeme kódovat jako $
A   // Počáteční symbol
// Přepisovací pravidla
A -> aBb | bCa
B -> aBb | $
C -> bCa | $

potom program najde řetězce

ab
aabb
ba
bbaa

Vizualizace odvozování řetězců generovaných gramatikou

Vytvořte program, který umožní vizualizovat odvozování řetězců postupným zadáváním přepisovacích pravidel. Gramatiku si program načte ze souboru. Poté vypíše jednotlivá přepisovací pravidla a startovací symbol. Například po načtení vystupního souboru

G2  //  Typ souboru
3   //  Počet prvků množiny neterminálních symbolů, neterminály jsou pak implicitně A,B,C
2   //  Počet prvků množiny terminálních symbolů, výstupy jsou pak implicitně a, b 
    //  prázdný řetězec budeme kódovat jako $
A   // Počáteční symbol
// Přepisovací pravidla
A -> aBb | bCa
B -> aBb | $
C -> bCa | $

by měl program vypsat přepisovací pravidla

1:  A -> aBb
2:  A -> bCa
3:  B -> aBb
4:  B -> $
5:  C -> bCa
6:  C -> $

Postupným výběrem přepisovacích pravidel (např. 1334) by měl program postupně vypisovat

A
1: aBb
3: aaBbb
3: aaaBbbb
4: aaabbb
(final)

Je-li ve větné formě několik neterminálních symbolů, přepisuje se nejlevější. Program neumožní zadat přepis pravidlem, které neodpovídá nejlevějšímu neterminálnímu symbolu z aktuální větné formy. Program musí umožňovat funkci undo (tj. krok zpět), a to až do startovacího symbolu.

Vizualizace principu Huffmanova kódování

Vytvořte program, který umožní krok po kroku sledovat činnost tvorby N-árního Huffmanova kódu pro zadaný vstup a následně ukáže, jak se vstup převede na výstupní kód. Programu se tedy zadá celé číslo N, pro jednoduchost 2 ≤ N ≤ 9, a vstupní řetězec, pro jednoduchost sestavený z malých písmen anglické abecedy.