HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Clearing a Confusion regarding the Proof of equal no of a's and b's not being a regular language

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
theequalregardingandregularbeingclearinglanguageconfusionnot

Problem

I was wondering about its proof. The direct use of pumping lemma here is not a viability. So a certain teacher of mine proved this with the notion that $a^{n}b^{n}$ being a subset of this language $L=\{w\mid\#_{a}(w)=\#_{b}(w)\}$ and non-regular (simple proof using pumping lemma) implies that the language $L$ can therefore not be regular!
The proof sounds alright initially but it got messy as I thought more on it!
I read in the books that the subset property of a regular language is not closed under regular languages. So, how can the proof be correct because for all I know L is a regular language that a non-regular language $a^{n}b^{n}$ as its subset. How does it say anything more?

I do know ofcourse that $L$ here is not regular and can draw production rules for it(CFG)! But, I need to clear this confusion I have above! Some help me here.

Solution

Here is what your teacher meant. Let $M=\{a^nb^n:n\geq0\} $. We know $M$ is not regular. Since the intersection of regular languages is regular, if $L$ were regular then so would $L\cap a^b^=M$ be, reaching a contradiction. This shows that $L$ cannot be regular.

Context

StackExchange Computer Science Q#29966, answer score: 5

Revisions (0)

No revisions yet.