95994

—    Przecięcie (iloczyn teoriomnogościowy) Li n L: = { x | x € Li a x € L2}

—    Dopełnienie języka L względem T 1 = T*-L

— Podstawienie

Podstawienie / jest odwzorowaniem alfabetu T na podzbiory zbioru V* dla pewnego alfabetu V. Zatem / przyporządkowuje każdemu symbolowi z T pewien język.

f: Th> 2^V*

Odwzorowanie / rozszerzamy na łańcuchy f: T* (-> 2^V* w następujący sposób:

(1)    f(e) = e

(2)    f(xa) = f(x)f(a)

Wreszcie odwzorowanie / rozszerzamy na zbiory łańcuchów, czyli na języki f: 2^t*    2^v*

definiując:

f(L)= U f(x)

X € L

Pizy kład:

Niech

T = {0,1}

V = {a, b}

f(0) = {a}

f( 1) = (bⁿ | n > 0} = {8, b, bb, bbb,...}

Wtedy dla lańcuclia 010 mamy

f(010) = {a> {bⁿ | n>0} {a} = {aa,aba,abba,abbba,...} = {ab“a | n>0}

Niech

L={0^ml | m>0} = {1,01,001,0001,...}

Wtedy

f(L)={a^,nbⁿ |m>0, n>0} =

= {e, b, bb, bbb,a, ab. abb abbb,aa, aab, aabb, aabbb, .., aaa, aaab, aaabb....}

Homomorfizm