正则语言regular language

FA={Q, ∑, 𝛿, q0, F}

representation: L-language, R-regular language, NR-nonregular language

∑={a,b}; notes: ø, {ε}, ∑* are all regular language

-----------------------------

L U ø = ø U L = L

L ∩ ø = ø ∩ L = ø

L o ø = ø o L = ø

L o ε = ε o L = L

------------------------------

regular closurse (proved)  <u n o is regular operation>

RUR=R; R∩R=R; RoR=R; ¬R=R

-------------------------------

else lemma:

RUNR=R|NR 

EX: {a,b}* U {a^n b^n| n≥0} = {a,b}*=∑* | ø U NR = NR

R∩NR=R|NR

EX: ø ∩ NR = ø | {a,b}* ∩ {a^n b^n| n≥0} = {a^n b^n| n≥0}

RoNR=R|NR

EX: ø o NR = ø | a o {a^n b^m| n≥0, m=n+1} = {a^m, b^m| m≥0}

------------------------------

NRUNR=R/NR

EX: {a^i b^j | i≤j} U {a^i b^j | i>j} = {a* b*} 

NR∩NR=R/NR

EX:  {a^i b^j | i<j} U {a^i b^j | i>j} = ø

NRoNR=R/NR

EX: ｜{a^i b^j | i>j} o {a^i b^j | i>j}= {a^i b^j a^i b^j | i>j}

------------------------------

对于判断是否为regular language不懂的看 (hint:fa无记忆)

https://math.stackexchange.com/questions/282216/determine-if-a-language-is-regular-from-the-first-sight

-------------------------------

regular ⊆ context-free ⊆ decidable(recursive) language ⊆ reconginzable language