Regularen jezik

Iz MaFiRaWiki

(Razlika med različicami)
Različica od 06:35, 20 december 2005
AndrejBauer (Pogovor | prispevki)

← Prejšnja različica
Različica od 13:32, 20 december 2005
AndrejStivicevic (Pogovor | prispevki)
malo dodatnih povezav
Naslednja različica →
Vrstica 1: Vrstica 1:
Družina '''regularnih jezikov''' nad abecedo <math>\Sigma</math> je opredeljena induktivno z naslednjimi pravili: Družina '''regularnih jezikov''' nad abecedo <math>\Sigma</math> je opredeljena induktivno z naslednjimi pravili:
# prazen jezik je regularen, # prazen jezik je regularen,
-# jezik <math>\{\epsilon\}</math>, ki vsebuje le prazno besedo, je regularen,+# jezik <math>\{\epsilon\}</math>, ki vsebuje le [[prazna beseda|prazno besedo]], je regularen,
# za vsak znak <math>a \in \Sigma</math> je <math>\{a\}</math> regularen, # za vsak znak <math>a \in \Sigma</math> je <math>\{a\}</math> regularen,
# če sta <math>L_1</math> in <math>L_2</math> regularna, so regularni tudi # če sta <math>L_1</math> in <math>L_2</math> regularna, so regularni tudi
-## unija <math>L_1 \cup L_2</math>,+## [[unija]] <math>L_1 \cup L_2</math>,
-## presek <math>L_1 \cap L_2</math>,+## [[presek]] <math>L_1 \cap L_2</math>,
-## produkt ali stik <math>L_1 \cdot L_2 = \{w_1 w_2 \mid w_1 \in L_1, w_2 \in L_2\}</math>+## [[produkt]] ali [[stik]] <math>L_1 \cdot L_2 = \{w_1 w_2 \mid w_1 \in L_1, w_2 \in L_2\}</math>
# Kleenejeva [[iteracija]] <math>L^{*}</math> regularnega jezika <math>L</math> je regularna. # Kleenejeva [[iteracija]] <math>L^{*}</math> regularnega jezika <math>L</math> je regularna.
-Iz teh pravil sledi, da je tudi komplement <math>\Sigma^* \setminus L</math> regularnega jezika regularen. Vsi končni jeziki so regularni.+Iz teh pravil sledi, da je tudi [[komplement]] <math>\Sigma^* \setminus L</math> regularnega jezika regularen. Vsi končni jeziki so regularni.
==Glej tudi== ==Glej tudi==

Različica od 13:32, 20 december 2005

Družina regularnih jezikov nad abecedo Σ je opredeljena induktivno z naslednjimi pravili:

  1. prazen jezik je regularen,
  2. jezik {ε}, ki vsebuje le prazno besedo, je regularen,
  3. za vsak znak a \in \Sigma je {a} regularen,
  4. če sta L1 in L2 regularna, so regularni tudi
    1. unija L_1 \cup L_2,
    2. presek L_1 \cap L_2,
    3. produkt ali stik L_1 \cdot L_2 = \{w_1 w_2 \mid w_1 \in L_1, w_2 \in L_2\}
  5. Kleenejeva iteracija L * regularnega jezika L je regularna.

Iz teh pravil sledi, da je tudi komplement \Sigma^* \setminus L regularnega jezika regularen. Vsi končni jeziki so regularni.

Glej tudi

Osebna orodja