Is this language regular?

Is the language L={asbtat-s ∣ 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 s-times, the b t-times and the second a (t-s)-times. It also tells me that s ≧ 0 and t ≧ s.

abbbaa | s=1 t=3 t-s=2
aabbba | s=2 t=3 t-s=1
aaabbb | s=3 t=3 t-s=0

So every word has an equal amount of a and b characters.

Pumping Lemma

  1. 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 aNbN seems ideal. And it is part of the language (see aaabbb example above)

  2. 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.
    Pumping Lemma

  3. After pumping the word k-times wk = aN+(k-1)bN is the result. The generated word can't be part of L because |a| != |b|. So the language is not regular.

Theo Winter

Theo Winter

Hi I'm Theo. I'm a developer, traveller, photo enthusiast, google-addict, macOS user from Switzerland.

Read More