Register

Non Regular Language

• retagged by
12,221 views
7 7 votes
Non regular language closed under which of the following operations?

I)Union

II) Intersection

III)Complementation

2 Answers

Best answer
29 29 votes

Set of Non-Regular languages is Closed under Complementation operation, But Not closed under Union or Intersection Operation.

MUST Watch this: Closure Properties of Non-Regular Languages 

1. Union Operation : Set of Non-Regular languages is NOT Closed under Union Operation.

For counter example, Consider  $L = \left \{ a^nb^n | n \geq 1 \right \}$ and $\overline{L}$...Both are Non-regular languages. But $L \cup \overline{L}$ = $\Sigma^*$ which is Regular language.

2. Intersection Operation : Set of Non-Regular languages is NOT Closed under Intersection Operation.

For counter example, Consider  $L = \left \{ a^nb^n | n \geq 1 \right \}$ and $\overline{L}$...Both are Non-regular languages. But $L \cap \overline{L}$ = $\phi$ which is Regular language.

3. Complementation Operation : Set of Non-Regular languages is Closed under Complementation Operation.

i.e. Complement of a Non-regular language is always a Non-regular language. 

We can prove it by Contradiction.

Let $L$ be any Non-regular language. Now, for contradiction purpose, Assume $\overline{L}$ be Regular.

Now, Since $\overline{L}$ is Regular, so,  $\overline{\overline{L}} $ = $L$ will be Regular, which Contradicts our assumption that $\overline{L} $ is non-regular. 

So, If $L$ is non-regular then $\overline{L}$ is necessarily non-regular.

We can say that $L$ is Regular if and only if $\overline{L} $ is Regular.

MUST Watch: Closure Properties of Non-Regular Languages

• edited by
0 0 votes
operations on which every type of languages are individually closed under are the following

..1..reversal

..2.. concatenation

..3.. intersection with regular

..4.. difference with regular

..5..inverse homomorphism

 

 

that's it.
• edited by
Voting & Accepting an answer helps improve the community
Answer:
← Previous · #DBMS Explain these ...Next → · Regular Language
← Previous in category · DFA constructionNext in category → · Regular Language
Position:
Show:

Related questions

1 1 vote
0 0 answers
827
827 views
dragonball asked Aug 16, 2017
827 views
Properties of Regular Language with Non- regular Language
Can anyone elaborate the properties of regular language with non regular under union, intersection, set difference , complement etc.
2 2 votes
1 1 answer
104
104 views
GO Classes asked Sep 21
104 views
GO Classes DPP | GATE CS | Theory of Computation | Regular Language
Let $M$ and $N$ be two DFAs. Define$$Z=\{u_1v_1u_2v_2\cdots u_kv_k : k\ge0, ~u_i\in L(M), ~v_i\in L(N)\}.$$Which regular-language expression describes $Z$?$L(M)^*L(N)^*$ ...
0 0 votes
1 1 answer
84
84 views
GO Classes asked Sep 21
84 views
GO Classes DPP | GATE CS | Theory of Computation | Regular Language
For an arbitrary language $L$, which of the following statements is correct?If $L^*$ is regular, then $L$ must be regular. If $L$ is nonregular, then $L^*$ must be nonreg...
0 0 votes
0 0 answers
179
179 views
lambodar_pal asked Jul 27
179 views
intersection of a context free language and a regular language
The intersection of a context free language and a regular languagea)need not be regularb)need not be context freec) is always regulard) is always context free