Operacije nad regularnimi jeziki

Skoči na: navigacija, iskanje

Operacije, ki ohranjajoi regularne jezike:

$Δ *$ je lahko druga abeceda

$s:\ \Sigma \rightarrow P(\Sigma^*)$

$a \rightarrow L_a$ vsako črko preslikamo v jezik

$x = a 1, a :2,... a n$

$S(x) = L_{a_1},....L_{a_n}$

$S(L) = U_{x \in L} S(x)$

Izrek: regularna substitucija ohranja regularne jezike

$h:\ \Sigma^* \rightarrow \ \Delta^*$

$h(\epsilon)\ =\ \epsilon$

$h(h_1 \bullet h_2) = h(x_1) \bullet h(x_2)$

homomorfizem deluje nad črkami

homomorfizem je neke vrste substitucija

$h:\ \Sigma^* \rightarrow \ \Delta^*$

$h^{-1}(L) = \{ x \in \Sigma^* | h(x) \in L \}$

L je jezik nad $Δ$

Izrek: $L \in \ RJ \ nad \ \Delta \ ; h: \Sigma^* \rightarrow \Delta^*, \ homomorfizem \rightarrow \ h^{-1} \ je \ regularni \ jezik$