So I found the following exercise and I have quite the trouble finding a way to solve it :
Having a alphabet {0,1,2,3,4} we define a set of words A, from that language in the following way(inductive definition of A) :
- 0,1 $\in$ A ,
- if $ \alpha \in A $, then $0\alpha \in A$ and $\alpha1 \in A $,
- if $ \alpha \in A $, then $42\alpha2 \in A$,
- if $\alpha,\beta \in A$ ,then $2\alpha3\beta2 \in A$;
Is it true that there exists a regular expression r, such that : L(r)=A
Assume $A$ is regular. For this language $A,$ the pumping lemma says that if $A$ is regular then there exists an integer $n$ such that for all $x\in A$ such that $|x|\geq n,$ there exist $u, v, w \in \{0,1,2,3,4\}^*$ such that
Given such an $n$, consider the string $x = (42)^n02^n,$ which is in $A.$ Then we must be able to write $(42)^n02^n=uvw$ where $u, v, w$ satisfy the conditions given above. But $uv$ is shorter than $(42)^n$ (note that $n\geq1$ by the conditions 2 and 3, so $n < 2n$), hence when we write $uv^2w$ we have just "pumped" some extra $4$s or $2$s into the $(42)^n$ part of $(42)^n02^n.$ As a result, the string $uv^2w$ has more than $2n$ symbols from $\{2,4\}$ before the $0,$ which implies that there are more than $n$ $2$s after the $0,$ but there are only $n$ of those (because $w$ includes the suffix $02^n$). This is a contradiction, so the assumption that $A$ is regular must be false.
That's a rough intuition of how the proof works. You would want to figure out a more formal argument.
Perhaps $x = 2^n0(302)^n$ would be an easier string to argue about, because then $uv = 2^m$ for $m\leq n$ and you can easily write $uv^2w$ in a form that shows it is not in $A.$