Domácí úkol – jazyk a jeho konečná reprezentace
Příklad 1 (10 bodů)
Porovnejte následujících 5 jazyků nad abecedou {a, b, c}∗ z hlediska množinových vztahů ⊂, ⊆, =.
• L1 = {a}∗ · {b, c}
• L2 = {a, b}∗ · {c}∗
• L3 = {a, b, c}∗
• L4 = {a, b}∗ · {b, c}∗
• L5 = {a}∗ · {a, b, c}+
Příklad 2 (10 bodů)
Pomocí jazyků L = {a}, K = {b} a množinových operací ∪, ∩, ·, iterace (*,+) a doplňku (co–)
vyjádřete následující 4 jazyky definované nad abecedou {a, b}:
• L1 obsahuje slova w taková, že |w| > 2.
• L2 obsahuje slova w taková, že #a(w) = 2k + 1, k ∈ N.
• L3 obsahuje slova w taková, že začínají a končí stejným symbolem.
• L4 obsahuje slova w taková, že řetězec abb není podslovem slova w.
• L5 obsahuje slova w taková, že |w| < 2 a zároveň #b(w) > 1.
1