Regularen jezik

Iz MaFiRaWiki

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 jezikov L_1 \cup L_2,
    2. presek jezikov L_1 \cap L_2,
    3. produkt jezikov L_1 \cdot L_2 = \{w_1 w_2 \mid w_1 \in L_1, w_2 \in L_2\}
  5. Kleenejeva iteracija jezika L * regularnega jezika L je regularna.

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

Glej tudi

Osebna orodja