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 ≥ 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 ≥ 0} = {ε, b, bb, bbb, ...}
Wtedy dla łańcucha 010 mamy:
f(010) = {a} {bn | n ≥ 0} {a} = {aa, aba, abba, abbba, ...} = {abna | n ≥ 0}
Niech
L = {0m1 | m ≥ 0} = {1, 01, 001, 0001, ...}
Wtedy
f(L) = {ambn | m ≥ 0, n ≥ 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 ≥ 0} = {a, aba, ababa, abababa, ...}
Wtedy
h-1(L) = {1}
Wyznaczmy h(h-1(L))
h(h-1(L)) = {aba} ≠ L
Widzimy, że:
... zobacz całą notatkę
Komentarze użytkowników (0)