2. Języki, gramatyki
2.1. Języki
Definicja języka
Niech T będzie alfabetem, T* - zbiorem wszystkich łańcuchów nad alfabetem T.
Dowolny podzbiór L zbioru T* nazywamy językiem L nad alfabetem T.
L Ä…" T*
Przykłady:
L0 = Ø - jÄ™zyk pusty
L1 = {µ} - jÄ™zyk zawierajÄ…cy tylko sÅ‚owo puste
L2 = T* - język zawierający wszystkie słowa nad alfabetem T
L3 = {µ, 0, 01, 001} - jÄ™zyk zawierajÄ…cy skoÅ„czonÄ… liczbÄ™ słów
L4 = {0, 01, 011, 0111, ...} = {01n | n e" 0} - język nieskończony
Operacje na językach
Niech L, L1 i L2 będą językami odpowiednio nad alfabetami T, T1 i T2.
L Ä…" T* L1 Ä…" T1* L2 Ä…" T2*
Najczęściej wykorzystuje się następujące operacje na językach:
% Suma teoriomnogościowa
L1 *" L2 = { x | x " L1 (" x " L2 }
% Złożenie języków
L1L2 = { x1x2 | x1 " L1 '" x2 " L2 }
% Domknięcie Kleene ego L*
L0 = {µ}
L1 = L
L2 = L1L
.................
Ln = Ln-1L
L* = L0 *" L1 *" L2 *" L3 *" ...
L+ = L1 *" L2 *" L3 *" ...
Rozpatruje się także operacje przecięcia (iloczynu teoriomnogościowego), dopełnienia,
podstawienia, homomorfizmu i ilorazu.
% Przecięcie (iloczyn teoriomnogościowy)
L1 )" L2 = { x | x " L1 '" x " L2 }
% Dopełnienie języka L względem T*
L = T* -L
% Podstawienie
Podstawienie f jest odwzorowaniem alfabetu T na podzbiory zbioru V* dla pewnego
alfabetu V. Zatem f przyporządkowuje każdemu symbolowi z T pewien język.
f: T 2V*
Odwzorowanie f rozszerzamy na łańcuchy
f: T* 2V*
w następujący sposób:
(1) f(µ) = µ
(2) f(xa) = f(x)f(a)
Wreszcie odwzorowanie f rozszerzamy na zbiory łańcuchów, czyli na języki
f: 2T* 2V*
definiujÄ…c:
f(L) = ółþÅ‚
ółþÅ‚
ółþÅ‚ f(x)
ółþÅ‚
x " L
Przykład:
Niech
T = {0, 1}
V = {a, b}
f(0) = {a}
f(1) = {bn | n e" 0} = {µ, b, bb, bbb, ...}
Wtedy dla łańcucha 010 mamy:
f(010) = {a} {bn | n e" 0} {a} = {aa, aba, abba, abbba, ...} = {abna | n e" 0}
Niech
L = {0m1 | m e" 0} = {1, 01, 001, 0001, ...}
Wtedy
f(L) = {ambn | m e" 0, n e" 0} =
= {µ, b, bb, bbb, ..., a, ab. abb. abbb, ..., aa, aab, aabb, aabbb, ..., aaa, aaab, aaabb, ...}
% Homomorfizm
Homomorfizmem h nazywany takie podstawienie, które każdemu symbolowi alfabetu T
przypisuje dokładnie jeden łańcuch ze zbioru V*, czyli homomorfizm to odwzorowanie:
h: T V*
Rozszerzamy odwzorowanie h na łańcuchy
h: T* V*
w taki sam sposób, jak to miało miejsce z podstawieniem:
(1) h(µ) = µ
(2) h(xa) = h(x)h(a)
Dalej rozszerzamy homomorfizm h na języki
h: 2T* 2V*
w taki sam sposób, jak podstawienie
h(L) = ółþÅ‚
ółþÅ‚
ółþÅ‚ h(x)
ółþÅ‚
x " L
Definiujemy przeciwobraz homomorficzny h-1(x) łańcucha x jako:
h-1(x) = {y | h(y) = x}
oraz przeciwobraz homomorficzny h-1(L) języka L jako:
h-1(L) = {x | h(x) " L}
Przykład:
Niech
T = {0, 1, 2}
V = {a, b}
h(0) = a
h(1) = aab
h(2) = ab
Wtedy dla łańcucha 012 mamy:
h(012) = aaabab
Niech
L = {01, 02}
Wtedy
h(L) = {aaab, aab}
Wyznaczmy h-1(h(L))
h-1(h(L)) = {002, 01, 02 1} `" L
Widzimy, że:
h-1(h(L)) ‡" L
Przykład:
Niech
T = {0, 1}
V = {a, b}
h(0) = aa
h(1) = aba
Niech
L = {(ab)na | n e" 0} = {a, aba, ababa, abababa, ...}
Wtedy
h-1(L) = {1}
Wyznaczmy h(h-1(L))
h(h-1(L)) = {aba} `" L
Widzimy, że:
h(h-1(L)) Ä…" L
% Iloraz języków
Niech będą dane dwa języki: L1 ą" T*, L2 ą" T*. Definiujemy iloraz L1/L2 tych języków
jako:
L1/L2 = { x | ( "
" y " L2) (xy " L1) }
"
"
Przykład:
Rozważamy języki:
L1 = {0n10m | m e" 0, n e" 0} = {1, 01, 10, 001, 010, 100, 0001, 0010, 0100, 1000, ...}
L2 = {10n1 | n e" 0} = {11, 101, 1001, 10001, ...}
L3 = {0n1 | n e" 0} = {1, 01, 001, 0001, ...}
Mamy:
L1/L2 = " gdyż każdy łańcuch y"L2 zawiera dwie jedynki, a każdy łańcuch xy"L1 może
zawierać tylko jedną jedynkę, więc nie istnieje łańcuch x, taki że xy"L1 i y"L2.
L1/L3 = {0n | n e" 0} = {µ, 0, 00, 000, ...} gdyż w rachubÄ™ wchodzÄ… tylko sÅ‚owa 1, 01, 001,
0001 z L1. i tylko słowo 1 z L3..
L2/L3 = {10n | n e" 0} = {1, 10, 100, 1000, ...}
Przedrostki, przyrostki
Niech z " L ą" T* będzie słowem z języka L.
Przedstawimy z w postaci:
z = xy x,y " T*
x nazywamy przedrostkiem (prefiksem) słowa z, zaś y nazywamy przyrostkiem (sufiksem)
słowa z.
x nazywamy przedrostkiem wÅ‚aÅ›ciwym sÅ‚owa z Ô! y `" µ.
y nazywamy przyrostkiem wÅ‚aÅ›ciwym sÅ‚owa z Ô! x `" µ.
Własność przedrostkowa i własność przyrostkowa języka
Język L ma własność przedrostkową gdy:
( " z "L ) ( " s  będącego przedrostkiem właściwym słowa z "L ) ( s " L )
czyli język ma własność przedrostkową, jeśli żaden przedrostek właściwy słowa tego języka
nie jest identyczny z żadnym słowem tego języka.
Język L ma własność przyrostkową gdy:
( " z "L ) ( " s  będącego przyrostkiem właściwym słowa z "L ) ( s " L )
czyli język ma własność przyrostkową, jeśli żaden przyrostek właściwy słowa tego języka
nie jest identyczny z żadnym słowem tego języka.
Przykład:
L = {10n | n e" 0} = {1, 10, 100, 1000, ...}
L nie posiada własności przedrostkowej, gdyż np. słowo 1000 ma przedrostek właściwy 10
będący słowem tego języka.
L posiada własność przyrostkową, gdyż wszystkie przyrostki właściwe słów tego języka mają
postać {0n | n e" 0}, i żaden z nich nie jest identyczny z żadnym słowem tego języka.