Why is the most constraint language for this not Regular and instead, Context-Free?

Question

This is the question: Q: Given the following production rules, which is finite or otherwise the most constrained language in the Chomsky language hierarchy corresponding to the language described by the following production rules?

Production Rules provided

From what I've read, for Regular Languages in Automata is that it can be constructed by a finite automaton & can't be a^nb^n and cannot have strings produced where we have to count part of the string to produce the rest of it. I'm just still quite confused on what it means when we cannot have strings produced where we have to count part of the string to produce the rest of it... (like just taking this particular question as an example) Could anyone help explain on this? Thanks a bunch.

Answer 1

The grammar is reproduced here:

S := aAbA
A := aAb
A := aba

Right off the bat, from the syntax of this grammar, we can guarantee the language at most context-free. This is because all productions have single non-terminals on the left-hand side. Given this, the most restrictive language class of the Chomsky hierarchy to which this language belongs must either be the regular languages or the context-free languages.

We can show this language is not regular using the pumping lemma for regular languages. Assume the language of this grammar were regular. Then for any string w in the language of the grammar of length at least p, it must be possible to write w = uvx where |uv| <= p, |v| > 0 and for all n >= 0, u(v^n)x is also a string in the language. Consider now the string a(a^p)aba(b^p)baba. This string is in the language of the grammar because we can derive it as follows:

S := aAbA := a(aAb)bA := aa(aAb)bba := ... := a(a^p)A(b^p)bA
  := a(a^p)aba(b^p)bA := a(a^p)aba(b^p)baba

This string has length at least p (indeed, its length is 2p + 8). As such, I should be able to write it in the manner described above; however, notice that the first p+1 symbols in this string are exclusively a. No matter how I write w = uvx, because |uv| <= p, uv consists only of a, and so must v. Thus, pumping only changes the number of a in the prefix of the string. But this cannot give me strings in the language for any n, since:

1. the grammar only generates intermediate forms with up to two instances of the non-terminal A
2. the non-terminal A can only cause the number of a to be exactly one greater than the number of b
3. all other productions in the grammar add the same numbers of a and b
4. as a result all strings produced by this grammar can only have two more a's than b's.
5. changing the number of a's in the prefix without changing the number of b's cannot maintain this characteristic of strings generated by the grammar

This is a contradiction. The only assumption we made was that the language is regular. Thus, we conclude the assumption was wrong and that the language cannot be regular.

Because the language is not regular, the most restrictive language class in the Chomsky hierarchy for it is the context-free languages.