Question

Define nor operation for the language as follows. nor(L1, L2) = {w : w E L1 or w E L2} Show that the family of regular languages is closed under the nor operation.

Answer 1

this is a very simple proof in which we will take help of other closure properties which are regular languages are closed under complement and regular language are closed under union.

Closure - it means that if you perform an operation on a type then in the result you will get same type. as we are saying regular languages are closed under union means when you will perform union operation on two regular languages then the resulted language will also be regular.

step 1: prove that regular language are closed under union

suppose L1, L2 regular ⇒ ∃ regexes R1, R2 s.t. L1 = L(R1) and L2 = L(R2). (means we have regular expression R1 which will derive language L1 and regular expression R2 which will derive language L2.)

⇒ L1 ∪ L2 = L(R1 ∪ R2) ⇒ L1 ∪ L2 regular. ( since union of regular expression is also a regular expression and there is always a regular language for every regular expression)

so this prooves that regular languages are closed under union.

step 2: proove that regular languages are closed under complement

suppose we have regular language L then there exist a DFA M = (Q, Σ, δ, q0, F) in which L=L(M)

now when you switch accepting states and non accepting states then you will get a finite automata machine which is M' and this will accept complement of regular language L' . as every finite automata has one regular language associated so M' will also generate a regular language.

which proves that regular languages are closed under complement.

step 3: now prove nor( L1,L2) = { w: wE :L1' or w E L2' } is closed under nor operation

now assume : L1 and L2 are regular languages so

L1' is also regular ( since regular language are closed under complement)

L2' is also regular ( since regular language are closed under complement)

now L1' U L2' is also regular ( since regular language are closed under union)

so result is a regular language which is the definition of nor operation. as or can be interpreted as union of the languages.

it proves that regular languages are closed under nor operation.

i hope it'll help you so please give positive ratings.