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$ Commented Sep 25, 2015 at 6:35
  • 1
    $\begingroup$ @Raphael You mean "well-specified" isn't well-specified?! :-) $\endgroup$ 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$ Commented Sep 25, 2015 at 8:21
  • $\begingroup$ By yes, do you mean true or false? $\endgroup$ Commented Sep 25, 2015 at 17:01

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.