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 '15 at 6:35
  • 1
    $\begingroup$ @Raphael You mean "well-specified" isn't well-specified?! :-) $\endgroup$ – 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}\}$.


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 '15 at 8:21
  • $\begingroup$ By yes, do you mean true or false? $\endgroup$ – Dude Sep 25 '15 at 17:01

Your Answer

