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}\}$.

| cite | improve this answer | |

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.

| cite | improve this answer | |
  • $\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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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