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.