patternMinor
Clearing a Confusion regarding the Proof of equal no of a's and b's not being a regular language
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.
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.