1
$\begingroup$

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?

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

2 Answers 2

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Sep 25, 2015 at 8:21
  • $\begingroup$ By yes, do you mean true or false? $\endgroup$
    – Sahil
    Commented 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.