Is this language regular?
Is the language L={a^{s}b^{t}a^{ts} ∣ 0 ≤ s ≤ t} using the alphabet ∑ = {a,b} regular? Let's find out.
One way to test if a language is regular is to use the pumping lemma approach. The concept of the pumping lemma is that a sufficiently long word can be pumped, meaning a middle section of the word is repeated a number of times to generate a new
word, that lies also within the same language.
So if the pumping lemma can be used to create a new word that is part of L, then L is regular and otherwise it isn't.
But first I want to get a feel for the language L. I want to see what sort of words it contains. The alphabet ∑ tells me that all words of L are made up of the characters a and b. And the language definition tells me that the first a appears stimes, the b ttimes and the second a (ts)times. It also tells me that s ≧ 0 and t ≧ s.
abbbaa  s=1 t=3 ts=2
aabbba  s=2 t=3 ts=1
aaabbb  s=3 t=3 ts=0
So every word has an equal amount of a and b characters.
Pumping Lemma

The first step is to chose a word to run the pumping lemma algorithm on. The word has to be long enough, so it should be ∣w∣ ≧ N. The word a^{N}b^{N} seems ideal. And it is part of the language (see aaabbb example above)

Next the word is split into xyz parts. ∣xy∣ ≤ N and ∣y∣ ≧ 1. The y part of the word has to consists entirely of the a character.

After pumping the word ktimes w_{k} = a^{N+(k1)}b^{N} is the result. The generated word can't be part of L because a != b. So the language is not regular.