Počet bodov: 3
Už odovzdalo: 10 ľudí (max. 10)

Zadanie:
Majme jazyk L nad abecedou Sigma = { a }. Zostrojme postupnosť c_i (i>=0) nasledovne: položíme c_i=1, ak aⁱ patrí do L a c_i=0, ak aⁱ do L nepatrí.

Teraz zostrojme desatinné číslo C tak, že za seba napíšeme všetky c_i ako cifry za desatinnou čiarkou (t.j. bude C = 0.c₀c₁c₂...).

Dokážte alebo vyvráťte tvrdenie: L je regulárny jazyk práve vtedy, keď číslo C je racionálne.

Príklad:
Pre prázdny jazyk L je C=0. Pre L = Sigma^* = {a}^* je C=0.111111111...=1/9.

Spôsob odovzdania:
Riešenie úlohy odovzdávajte spísané v elektronickej podobe mailom na misof@ksp.sk, v subjecte uvedte FOJA premia 3. Akceptujú sa otvorené formáty, menovite .tex, .dvi, .ps, .pdf, (ak ináč nejde) .txt. (Používať M$ Word neodporúčame, ak sa však predsa len rozhodnete písať v ňom, môžete vytvoriť súbor .ps tak, že nainštalujete driver pre PostScriptovú tlačiaren a príslušný .doc dáte vytlačiť do súboru.)