# Are there well-specified formal languages that are not regular?

Given a finite alphabet, there are well-specified formal languages that can not be recognized by regular expressions, FSAs or regular grammars True/False

I am studying for my exam and I am unsure about this question. From my understanding, you generate formal languages from regex, FSA. For i.e. for a* our formal language will be

empty,a,aa,aaa etc.

So I can identify if a formal language can be described by a regex, but not sure if that is always the case. Could somebody please help me with this?

• Define "well-specified". – Raphael Sep 25 '15 at 6:35
• @Raphael You mean "well-specified" isn't well-specified?! :-) – David Richerby Sep 25 '15 at 8:38

## 2 Answers

There are indeed well-specified formal languages that cannot be represented by regular expressions, even on a one-letter alphabet. Examples include $\{a^{n^2} \mid n > 0\}$ and $\{a^p \mid p \text{ is a prime number}\}$.

If "well-specified" does not have a very special meaning in your course, than the answer is "yes"; it follows directly from e.g.

$\qquad\displaystyle \mathrm{REG} \subsetneq \mathrm{CFL} \subsetneq 2^{\Sigma^*}$,

a result that was probably presented in the course.

• You are right, but the OP's example was on a one-letter alphabet. And in this case, REG = CFL. – J.-E. Pin Sep 25 '15 at 8:21
• By yes, do you mean true or false? – Dude Sep 25 '15 at 17:01