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?

  • 2
    $\begingroup$ Define "well-specified". $\endgroup$
    – Raphael
    Sep 25, 2015 at 6:35
  • 1
    $\begingroup$ @Raphael You mean "well-specified" isn't well-specified?! :-) $\endgroup$ Sep 25, 2015 at 8:38

2 Answers 2


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.