IB102 - úkol 4
Odevzdání: 24.10. 2011
Vypracoval (a): Skupina:
UCO:
1. [2 body]
a) Uvažme abecedu E = {a} a relaci Ra nad E* definovanou takto:
uRav •<=>- \u\ mod 3 = 0 A \v\ mod 3 = 0.
• Rozhodněte, která slova z množiny {e, a, aa, aaa, aaaa} jsou spolu v relaci a která nikoliv a výsledek znázorněte do obrázku níže, tj. spojte šipkou vedoucí z u do v všechna u a, v taková, žeuRav. Pokud u Ra v i v Ra u, můžete použít " dvojšipku"-jednu čáru se šipkami na obou koncích. Nezapomeňte udělat šipku z u do u v případě, že uRau.
• Je Ra ekvivalence? Zdůvodněte.
• Je Ra pravá kongruence? Zdůvodněte.
b) Proveďte totéž pro relaci R^ nad E* definovanou takto:
uR^v <í=^ (\u\ mod 3 = 0 <í=^ \v\ mod 3 = 0).
b)
e
aaaa •
• a
aaaa •
• a
aaa
aa
aaa
aa
Bonus: [+1 bod]
c) Proveďte totéž pro relaci Rc nad E* definovanou takto:
uRcv <í=^ (\u\ mod 3 = 0 =>• \v\ mod 3 = 0).
c)
aaaa • • a
aaa aa
IB102 - úkol 4
Odevzdání: 24.10. 2011
Vypracoval (a): UČO: Skupina:
2. [2 body] Rozhodněte a zdůvodněte, zda platí:
• Existuje regulární jazyk L C {a, b}* a pravá kongruence ~ na {a, b}* taková, že L je sjednocením některých tříd rozkladu {a, b}* podle ~ a index ~ je dvojnásobkem indexu
• Existuje regulární jazyk L C {a, b}* a pravá kongruence ~ na {a, b}* taková, že L je sjednocením některých tříd rozkladu {a, b}* podle ~ a index ~l je dvojnásobkem indexu ~.
(Pozn. Pokud bude Vaše odpověď "ano, platí", uveďte zcela konkrétní příklad takového jazyka L a pravé kongruence ~, a zdůvodněte. Pokud bude Vaše odpověď "ne, neplatí", pokuste argumentovat, proč to neplatí pro žádný jazyk L a žádnou pravou kongruenci ~).
Bonus: [+1 bod]
Jak by se změnily odpovědi, pokud bychom netrvali na regularitě jazyka LI Zdůvodněte.