Question

Non regular language closed under which of the following operations?

I)Union

II) Intersection

III)Complementation

Comments

Non as

DCFL not closed under union

CFL not closed under intersection

CFL not closed under complement

---

DCFL not closed under union

CFL not closed under intersection

CFL not closed under complement

This logic is Not correct to check Closer. Though it has somehow given Two correct results (Not closed under Union and Intersection) ...The third result is Wrong. Set of Non-Regular languages is Closed under Complementation Operation.

---

https://www.google.com/url?sa=t&source=web&rct=j&url=https://www.cs.unc.edu/~plaisted/comp455/slides/cfl3.5.pdf&ved=2ahUKEwiL3-zk1cvkAhUgmI8KHXQCASAQFjABegQIDxAG&usg=AOvVaw1qMYY0I_sLXgWpub7tIg9D

 

@Deepakk Poonia (Dee)

the meaning is complemented non regular languages are always non regular  they doesn't become regular. 

Answer 1

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

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.

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

We can prove it by Contradiction. Let $L$ be a Non-regular language, and let $\overline{L}$ be Regular. Then, Since $\overline{L}$ is Regular, so,  $\overline{\overline{L}} $ = $L$ will be Regular. Which Contradicts our assumption that $\overline{L} $ is non-regular. 

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

Comments

For (3) we can also  say that when we take complement of  non regular languages( dcfl,cfl ,re,not re ),they will still remain non regular for example -$a^nb^n$ is non regular when we take complement of this ,it will still remain non regular.so non regular languages are closed under complement.

---

The explanation that you gave for 1 tells about union of two context free languages and not about two non regualar languages. The explanation 1 cant fit for proving two non regualar languages

---

The explanation that you gave for 1 tells about union of two context free languages and not about two non regualar languages. The explanation 1 cant fit for proving two non regualar languages

But those two CFLs are Non-Regular. So, It is valid explnation.  

---

Theorem:

Concatenation of two non-regular languages can be regular.

Constructive Proof:

Let $L$ be any non-regular language. Now, we know $L’$ is also non-regular.

Consider $(L \cup \{ \epsilon \})$ ; $(L’ \cup \{ \epsilon \})$, both of which are non-regular.

Now, $(L \cup \{ \epsilon \}).(L’ \cup \{ \epsilon \}) = \Sigma^*$, which is regular.

---

For concrete example:

Consider $L =$ Set of All Prime Numbers over $\{ 0 \}$ , 

$M =$ Set of All Composite Numbers over $\{ 0 \}$

Both $L,M$ are Non-regular.

Now, $L.M = \{ 0^n , n \geq 6 \}$ which is regular.

Answer 2

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.