Łańcuchy, języki



Pobieranie 48,94 Kb.
Data23.10.2017
Rozmiar48,94 Kb.

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 }

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*



  • 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:

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  0, n  0} = {1, 01, 10, 001, 010, 100, 0001, 0010, 0100, 1000, ...}

L2 = {10n1 | n  0} = {11, 101, 1001, 10001, ...}

L3 = {0n1 | n  0} = {1, 01, 001, 0001, ...}

Mamy:


L1/L2 =  gdyż każdy łańcuch yL2 zawiera dwie jedynki, a każdy łańcuch xyL1 może zawierać tylko jedną jedynkę, więc nie istnieje łańcuch x, taki że xyL1 i yL2.

L1/L3 = {0n | n  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  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  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  0}, i żaden z nich nie jest identyczny z żadnym słowem tego języka.

Uporządkowanie leksykograficzne

Niech R będzie relacją dobrego porządku na zbiorze (alfabecie) T. Zdefiniujemy relację R' określoną na T+. Powiemy, że x = a1a2...am jest w relacji R' z y = b1b2...bn (xR'y; x,yT+; ai,bjT dla 1  i  m, 1  j  n), gdy spełniony jest jeden z dwóch poniższych warunków:



  1. aiRbi dla pewnego  m oraz aj = bj dla wszystkich  j < i

  2.  n oraz ai = bi dla wszystkich  i  m.

Dowodzi się, że R' jest relacją dobrego porządku na zbiorze T+. Wobec tego można wszystkie łańcuchy należące do T+ ułożyć w ciąg i ponumerować (rozpoczynając od 1) – stąd wniosek, że zbiór T+ dla dowolnego (skończonego) alfabetu T jest równoliczny ze zbiorem liczb naturalnych. Jeśli do powyższego ciągu dodamy jeszcze łańcuch pusty i ustawimy go przed wszystkimi łańcuchami niepustymi nadając numer zero (tzn. przyjmiemy, że  R' x dla dowolnego łańcucha  T*), otrzymamy uporządkowanie zbioru T* i potwierdzenie jego równoliczności ze zbiorem liczb naturalnych. W taki sam sposób można uporządkować słowa dowolnego języka  T* (określając relację R na alfabecie T oraz redukując relację R' określoną na T* do L). Mówimy wówczas o leksykograficznym porządku słów danego języka.

Przykładem porządku leksykograficznego R' może być uporządkowanie słów w encyklopediach, słownikach, leksykonach – wówczas R jest powszechnie przyjętym uporządkowaniem liter w alfabecie pewnego języka naturalnego.



©operacji.org 2017
wyślij wiadomość

    Strona główna