Register

Complement of Nonregular Language

• edited by
1,116 views

3 Answers

6 6 votes
No, for any regular language $R$, $R'$ is also regular (regular language is closed under complement). Now, suppose if there exists a non-regular language $L$ whose complement $L'$ is regular when we take the complement of $L'$ we get $L'' = L$ which is not regular and is violating the closure property. So, by the proof of contradiction, no such non-regular language can exist whose complement is regular.
0 0 votes
Prove it by contradiction .

let a language L which is Non regular and whose complement L' is regular.

Now as L' is regular and we know Regular languages are closed under complement so (L')' would also be regular.

But we also know (L')' =L so ultimately we proved  L=Regular but as we considered L as non regular so by contradiction the complement of non regular language can't be regular.
0 0 votes

Detailed Video Solution: Complement of a Non-Regular Language is Always Non-regular

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

Voting & Accepting an answer helps improve the community
← Previous · #GoClassroomNext → · ME Gate, 2014
← Previous in category · Digital ElectronicsNext in category → · http://www.cs.rice.e...
Position:
Show:

Related questions

1 1 vote
1 1 answer
56
56 views
GO Classes asked 5 days ago
56 views
GO Classes DPP | GATE CS | Theory of Computation | Nonregular Union
Suppose $L_1$ and $L_2$ are both nonregular languages.Which statement about $L_1\cup L_2$ is correct?It must be nonregular. It must be regular. It may be regular or nonre...
1 1 vote
1 1 answer
43
43 views
GO Classes asked 5 days ago
43 views
GO Classes DPP | GATE CS | Theory of Computation | Nonregular Reversal
Let $L$ be a nonregular language.What can always be concluded about $L^R$?$L^R$ is regular. $L^R$ is nonregular. $L^R$ may be regular or nonregular. Nothing can be conclu...
2 2 votes
1 1 answer
81
81 views
GO Classes asked Sep 21
81 views
GO Classes DPP | GATE CS | Theory of Computation | Language Quotient
For languages $X,Y\subseteq\Sigma^*$, define$$X/Y = \{w:\exists y\in Y,\ wy\in X\}$$ Suppose $X$ is regular, but nothing is assumed about $Y$.Which statement is always tr...
2 2 votes
1 1 answer
65
65 views
GO Classes asked Sep 21
65 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)^*$ ...