# 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?

## migrated from stackoverflow.comSep 25 '15 at 3:03

This question came from our site for professional and enthusiast programmers.

• 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

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}\}$.
$\qquad\displaystyle \mathrm{REG} \subsetneq \mathrm{CFL} \subsetneq 2^{\Sigma^*}$,