Proving that there is a sequence of letters in all words of a formal language

51 Views Asked by At

I have a formal language that contains all words that have twice as many b's as a's, for example aabbbb. Now I'm trying to prove that there always must be atleast one sequence of 3 letters inside given word that are either bab, bba or abb. It's a part of a bigger proof that I'm making but it's crucial for it to work and I struggle with it. It looks quite obvious that it must be the case, but how can I prove it? Any hints?

1

There are 1 best solutions below

1
On BEST ANSWER

Assume first that the word has at least 2 a's. Then the word must contain two consecutive b's, for otherwise each b would immediately be followed by at least one a, and there could not be twice as much b's as a's in the word. Thus, consider such a sequence of at least 2 consecutive b's. Either at the beginning or at the end of this sequence, there must be an a. Hence, either abb or bba is contained. If the word has only one a, then there need not be two consecutive b's, but this is possible only for the word bab.