This is a grammar and I wan to check if this language is regular or not.
L → ε | aLcLc | LL
For example the result of this grammar is:
acc, accacc ..., aacccc, acaccc, accacc, aaacccccc, ...
I know that is not a regular language but how to prove it? Is building an automata the right way to prove it? What is the resulting automata. I don't see pattern to use it for build the automata.
Thank you for any help!
First, let me quickly demonstrate that you cannot deduce the language of a grammar is irregular based solely on the grammar's being irregular. To see this, consider the unrestricted grammar:
S -> SSaSS | aS | e
SaS -> aSa
aaS -> SSa
This is clearly not a regular grammar but you should be able to verify it generates the infinite regular language of all strings of a.
That said, how should we proceed? We will need to figure out what language your grammar generates, and then argue that particular language cannot be regular. We notice that the only rule that introduces terminal symbols always introduces twice as many c as it does a. Furthermore, it's not hard to see the language must be infinite. We can use the Myhill-Nerode theorem to show that these observations imply the language must be irregular.
Consider the prefix a^n of a hypothetical string in the language of this grammar. The shortest string which can be appended to the end of this prefix to give us a string generated by this grammar is c^(2n). No shorter string will work, and that string always works. Imagine now that we were looking at a correct deterministic finite automaton for the language of the grammar. Then, whatever state processing the prefix a^n left us in, we'd need the shortest path from there to an accepting state in the automaton to have length 2n. But a DFA must have finitely many states, and n is an arbitrary natural number. Our DFA cannot work for all possible n (it would need to have arbitrarily many states). This is a contradiction, so there can be no correct DFA for the language of the grammar. Since all regular languages have DFAs, that means the language of this grammar cannot be regular.