Kalábovi - pitel:tin:ukoly:2011

Úkol 1

anonymous@undisclosed.example.com (Anonymous) — Fri, 30 Dec 2022 13:43:01 +0000

Úkol 1 Bc. Jan Kaláb Příklad 1 Uvažte jazyk L1 = {aibj | 0 < i ≤ j ∧ i + j = 2k, k ∈ ℕ}. Sestavte gramatiku G1 takovou, že L(G1) = L1. G1 = ({a, b}, {S, X, Y}, S, P) P = { * S → aXbY * X → aXb

Úkol 2

anonymous@undisclosed.example.com (Anonymous) — Fri, 30 Dec 2022 13:43:01 +0000

Úkol 2 Bc. Jan Kaláb Příklad 1 Uvažte jazyk L₁ = {wcⁱ | w ∈ {a, b}* ∧ (#a(w) = i ∨ #b(w) = i)}. Sestavte gramatiku G₁ takovou, že L(G₁) = L₁. G₁ = ({S, A, B}, {a, b, c}, P, S) P: * S → A

Úkol 3

anonymous@undisclosed.example.com (Anonymous) — Fri, 30 Dec 2022 13:43:01 +0000

Úkol 3 Bc. Jan Kaláb Příklad 1 Popište pomocí kompozitního diagramu jednopáskový Turingův stroj M, který provádí sčítání dvou čísel ve dvojkové soustavě. Pokud bude vstupní kofigurace pásky ΔA#B

Úkol 4

anonymous@undisclosed.example.com (Anonymous) — Fri, 30 Dec 2022 13:43:01 +0000

Úkol 4 Bc. Jan Kaláb Příklad 1 Pomocí počátečních funkcí, a operátorů kombinace, kompozice a primitivní rekurze výjádřete funkci počítající zbytek po celočíselném dělení: mod: ℕ² → ℕ, mod