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

?