IB102 ­ úkol 1 ­ řešení Odevzdání: 22. 9. 2008
Vypracoval: James Bond UČO: 007
Skupina: MI6
1. [2 body] Zapište, kolik různých slov patří do jazyka L nad abecedou  = {a, b}, pokud:
L1 = {, a} L2 = {, ab} L3 = {a, b} L4 = (L1  L2)+
 (L2
3)
(L3
3  L
3)
L = L4  ((L3  L1) L3) L
3  (L1  L3)
Odpověď zdůvodněte.
Řešení: Zápis jazyka L4 upravíme pomocí množinové algebry na ekvivalentní tvar:
L4 = (L1  L2)+
 (L2
3)
(L3
3  L
3)
Protože (L2
3)
je jazyk všech slov sudé délky a L3
3  L
3 je jazyk všech slov délky 3 a větší,
jejich rozdílem je jazyk všech slov délky 0 a 2, tedy jazyk {, aa, ab, ba, bb}. Jelikož L1  L2 =
{, a, ab, aab}, lehce spočítáme L4:
L4 = {, a, ab, aab}+
 {, aa, ab, ba, bb} = {, aa, ab}
Dále (L3  L1) L3 = {a, b, aa, ba} {a, b} = {aa, ba}, tedy:
L = {, aa, ab}  {aa, ba} L
3  (L1  L3) = {, aa, ab, ba} L
3  {a}
Jazyk L
3  {a} obsahuje právě slova, jejichž suffixem je a. Celkem dostáváme L = {, ab}.
Do jazyka L tedy patří 2 různá slova.
IB102 ­ úkol 1 ­ řešení Odevzdání: 22. 9. 2008
Vypracoval: James Bond UČO: 007
Skupina: MI6
2. [2 body] Nechť L je jazyk nad abecedou  = {0, 1} tvořený právě všemi slovy, která
splňují následující podmínku:
Pokud je slovo liché délky, pak má prefix 01 a sufix 10.
Zapište jazyk L pomocí jednoprvkových jazyků {0} a {1} a s využitím operací průnik (),
sjednocení (), zřetězení () a iterace (
,+
).
Řešení: Implikaci lze přepsat do tvaru ,,Slovo má sudou délku, nebo má prefix 01 a suffix
10". Pomocné označení:
jazyk slov délky 1 nad abecedou : L1 = {0}  {1}
jazyk slov sudé délky: L2 = (L1  L1)
jazyk slov s prefixem 01 a suffixem 10: L3 = ({0}  {1}  L
1)  (L
1  {1}  {0})
Hledaný jazyk L pak je L2  L3.