lower,urządzenia obiektowe automatyki,jezyki.pdf

(100 KB) Pobierz
24735651 UNPDF
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
, 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 .
T 2 *
Najczęściej wykorzystuje się następujące operacje na językach:
─ Suma teoriomnogościowa
L
T *
L 1
T 1 *
2
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
...
...
Rozpatruje się także operacje przecięcia (iloczynu teoriomnogościowego), dopełnienia,
podstawienia, homomorfizmu i ilorazu.
L + = L 1
L 2
L 3
L 3 = {
─ 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:
(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
(1) f(
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:
(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)
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:
x
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
(1) h(
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 .
, 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} = {
0} = {1, 10, 100, 1000, ...}
T * będzie słowem z języka L .
Przedstawimy z w postaci:
L
z = xy
x,y
T *
L 1 /L 3 = {0 n | n
Przedrostki, przyrostki
Niech z
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:
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 przedrostkiem 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
z
L ) (
s – będącego przyrostkiem właściwym słowa z
L ) ( s
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.
(
(

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin