Describe in words why the following languages over the alpha

Describe in words why the following languages over the alphabet,
= {a, b}
are nonregular:

a) PAL = {palindromes}
b) EQAB = {strings that contain the same number of a\'s and b\'s}

Solution

a) given PAL = { Palindromes } if we can able build a finite automata for given L then language is regular...

Now we write PAL as { WWr} , for W we can build FA, M1

and for Wr (reverse of W) , we can build FA, M2

Now concatenate M1 and M2 with epsilon transition, (epsilon transition from final state in M1 to initial state in M2 resulting NFA

since, we have built NFA for given PAL the language pal is regular

B) given EQAB has equal number of a\'s and b\'s, so to compare whether the a\'s and b\'s in string equal or not we need a stack, FA does not have stack, so we can\'t build FA for this language, hence it is non regular