-1
$\begingroup$

Consider the language $$L = \{w \mid w \text{ has an unequal number of a’s and b’s}\}$$ where Σ = {a, b}. Prove that L is not regular. Hint: Try proof by contradiction.

Would this be the right Answer:

L = {a^m b^n | m < n} U {a^m b^n | m > n}

Looking at this we can tell that a is more than b or a is less than b. They depend on each other. Thus we can tell that language L is not regular, because we can conclude dependency. Dependency needs a stack to compare to one another. Finite automata does not have a stack.

$\endgroup$
1
  • $\begingroup$ These two $L$s are not equivalent. For instance $aba$ is in the first one but not the second one. Try to consider closure properties to tackle this question. $\endgroup$ – Ran G. Apr 24 at 10:25
1
$\begingroup$

What you explained cannot be called a formal proof. Its only within the scope of intuition. A formal proof needs formal arguments, using theorems and or lemmas along the way.

Anyways, try to think of $L^c$ (the complement of $L$). Is this language regular? What is the connection between $L^c$ and $L$ in those terms?

$\endgroup$
0
$\begingroup$

Assume the language is regular, then it can be implemented using a finite state machine with k states.

If you parse a string starting with a^k then you must enter some state X twice, parsing a^j for some 1 <= j <= k to get from X back to X. You could remove that string a^j from your input and reach the same state parsing the whole string.

Now take the strings a^(k+j)b^k and a^kb^k. One is in the language, the other isn’t, but they end in the same final state, so they must be both in the language of both not in the language.

Of course that’s just the pumping Lemma...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.