Is the language of all lines above the alphabet "a, b, c" with the same number of substrings "ab" and "ba" regular?

Is the language of all lines above the alphabet "a, b, c" with the same number of substrings "ab" and "ba" regular?

I think the answer is NO, but it’s hard to make an official demonstration, even an informal one.

Any ideas on how to approach this?

+4
source share
2 answers

This is clearly not regular. How FA recognizes (abc) ^ nc (cba) ^ n. Strings like this in your language, right? The argument is simple, based on the fact that there are an infinite number of equivalence classes with the indistinguishability relation I_l.

+2
source

The most common way to prove a language is NOT regular is to use Pumping Lemmas .

Using the lemma is a bit complicated, since it has all of these β€œexist”, etc. To prove that the language L is not regular, using the pumping lemma, you must prove that

for any integer p, there is a word w in L of length n, with n>=p, such that for all possible ways to decompose w as xyz, with len(xy) <= p and y non empty there exists an i such that x(y^i)z (repeating the y bit i times) is NOT in L 

Whooo!

I will show how the proof looks for "the same number of characters as and bs". To convert to your case, it should be easy:

 for any given p, we can make a word of length n = 2*p a^pb^p (pa followed by p b's) any way you decompose this into xyz w/ |xy| <=p, y will only contain a's. Thus, pumping the the y part will make the word have more as than bs, thus NOT belonging to L. 

If you need an intuition about why this works, this follows from how you need to be able to count to massive numbers in order to check whether a word belongs to one of these languages. However, regular languages ​​are described by finite automata, and no finite automata can represent an infinite number of states needed to represent all numbers. (The Wikipedia article must have official proof).


EDIT: It seems you cannot directly use the pumping lemma in this particular case directly: if you always make y single character, you can never make the word stop being accepted (aba becomes abbbba does not make a difference, etc.).

Just take the equivalence class approach proposed by Patrick87 - it will probably turn out to be cleaner than any of the dirty hacks that you will need to do in order to apply the applicable pumping lemma.

0
source

All Articles