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:
L
0
= Ø
- język pusty
L
1
= {
ε
} -
język zawierający tylko słowo puste
L
2
= T
*
- język zawierający wszystkie słowa nad alfabetem T
L
3
= {
ε
, 0, 01, 001}
-
język zawierający skończoną liczbę słów
L
4
= {0, 01, 011, 0111, ...} = {01
n
| n
≥
0}
- język nieskończony
Operacje na językach
Niech L, L
1
i L
2
będą językami odpowiednio nad alfabetami T, T
1
i T
2
.
L
⊆
T
*
L
1
⊆
T
1
*
L
2
⊆
T
2
*
Najczęściej wykorzystuje się następujące operacje na językach:
─ Suma teoriomnogościowa
L
1
∪
L
2
= { x | x
∈
L
1
∨
x
∈
L
2
}
─ Złożenie języków
L
1
L
2
= { x
1
x
2
| x
1
∈
L
1
∧
x
2
∈
L
2
}
─ Domknięcie Kleene’ego L*
L
0
= {
ε
}
L
1
= L
L
2
= L
1
L
.................
L
n
= L
n-1
L
L
*
= L
0
∪
L
1
∪
L
2
∪
L
3
∪
...
L
+
= L
1
∪
L
2
∪
L
3
∪
...
Rozpatruje się także operacje przecięcia (iloczynu teoriomnogościowego), dopełnienia,
podstawienia, homomorfizmu i ilorazu.
─ Przecięcie (iloczyn teoriomnogościowy)
L
1
∩
L
2
= { x | x
∈
L
1
∧
x
∈
L
2
}
─ 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 ! 2
V*
Odwzorowanie f rozszerzamy na łańcuchy
f: T
*
! 2
V*
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: 2
T*
! 2
V*
definiując:
f(L) =
f(x)
x
∈
L
Przykład:
Niech
T = {0, 1}
V = {a, b}
f(0) = {a}
f(1) = {b
n
| n
≥
0} = {
ε
, b, bb, bbb, ...}
Wtedy dla łańcucha 010 mamy:
f(010) = {a} {b
n
| n
≥
0} {a} = {aa, aba, abba, abbba, ...} = {ab
n
a | n
≥
0}
Niech
L = {0
m
1 | m
≥
0} = {1, 01, 001, 0001, ...}
Wtedy
f(L) = {a
m
b
n
| 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: 2
T*
! 2
V*
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)
n
a | n
≥
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: L
1
⊆
T
*
, L
2
⊆
T
*
. Definiujemy iloraz L
1
/L
2
tych języków
jako:
L
1
/L
2
= { x | (
∃∃∃∃
y
∈
L
2
) (xy
∈
L
1
) }
Przykład:
Rozważamy języki:
L
1
= {0
n
10
m
| m
≥
0, n
≥
0} = {1, 01, 10, 001, 010, 100, 0001, 0010, 0100, 1000, ...}
L
2
= {10
n
1 | n
≥
0} = {11, 101, 1001, 10001, ...}
L
3
= {0
n
1 | n
≥
0} = {1, 01, 001, 0001, ...}
Mamy:
L
1
/L
2
=
∅
gdyż każdy łańcuch y
∈
L
2
zawiera dwie jedynki, a każdy łańcuch xy
∈
L
1
może
zawierać tylko jedną jedynkę, więc nie istnieje łańcuch x, taki że xy
∈
L
1
i y
∈
L
2
.
L
1
/L
3
= {0
n
| n
≥
0} = {
ε
, 0, 00, 000, ...}
gdyż w rachubę wchodzą tylko słowa 1, 01, 001,
0001 z L
1
. i tylko słowo 1 z L
3
..
L
2
/L
3
= {10
n
| n
≥
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 = {10
n
| n
≥
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ć {0
n
| n
≥
0}, i żaden z nich nie jest identyczny z żadnym słowem tego języka.