Všechny úlohy uvažujte nad abecedou Σ = {a, b}.
1. Popište Σ∗
/∼L (tj. rozklad množiny všech slov podle prefixové ekvivalence jazyka L), kde:
a) L = ∅;
b) L = {a12
};
c) L = {a3
, a7
, a4
b4
, b4
a4
};
d) L = {w ∈ Σ∗
: #a(w) = #b(w)};
e) L = {w ∈ Σ∗
: |w| ≥ 42};
f) L = {an
bn
| n ∈ N};
g) L = {w ∈ Σ∗
: w = wR
}.
2. Pro každé n ≤ 6 určete počet pravých kongruencí, které respektují jazyk {w ∈ Σ∗
: |w| mod 4 = 0}
a jejichž index je n.
3. Uvažme pravé kongruence ∼1, . . . , ∼5 definované následujícími předpisy (x, y ∈ Σ∗
):
x ∼1 y ⇔ x a y končí na stejné písmeno1
x ∼2 y ⇔ x a y začínají na stejné písmeno1
x ∼3 y ⇔ |x| mod 6 = |y| mod 6
x ∼4 y ⇔ (x ∼1 y ∧ x ∼3 y)
x ∼5 y ⇔ (x ∼2 y ∧ x ∼3 y)
Pro každé i ∈ {1, . . . , 5} určete:
a) kolik existuje jazyků, které ∼i respektuje;
b) kolik existuje jazyků, jejichž prefixovou ekvivalencí je ∼i.
4. V závislosti na n ∈ N určete:
a) kolik existuje konečných neprázdných jazyků, jejichž nejdelší slova mají délku n;
b) jaký nejmenší a největší index mají prefixové ekvivalence jazyků z a).
1ε je v relaci jen se sebou