Show that the language L w naw nbw is not regular Is L r

Show that the language L = {w : n_a(w) = n_b(w) } is not regular. Is L* regular?

Solution

Pumping Lemma states that for any regular language there is a value m so that if you pick any string of the language with a length greater than m, then we can always find a nonempty portion y of the string that appears in the string within the first m characters that can be “pumped”, i.e. repeated as many times as we like, forming strings that are always in the language. The key here is to find a counterexample, a string in the language of length >= m, for which it will be easy to show that there is no way to pump it. Proof: Assume L is regular. Therefore the Pumping Lemma holds for L.  Consider the string ambm. This string is clearly longer than m and clearly belongs to the language because the number of a’s = the number of b’s. By the Pumping Lemma, this string can be represented as xyz with |xy| m and y nonempty, so that xyi z is in L for all values of i. But since the length of xy is m and there are m a’s at the start of the string, xy (and also y) must consist of only a’s. So y = ak with k > 0. String xy2 z is am+kbm, because we have added another y (or ak ) to the string. But the number of a’s here does not equal the number of b’s, so this string is NOT in the language.  This contradicts the Pumping Lemma

so given language is not regular

L is not regular then L* also not regular