1
$\begingroup$

A regular language is a language that can be represented by a regular expression(or for which there exists a DFA), then why is language represented by 0$^{+}$ not regular?

I am asking this because for the following question the correct answer is option 2

Let L denote the languages generated by the grammar S→0S0∣00. Which of the following is TRUE?

  1. L=0$^{+}$

  2. L is regular but not 0$^{+}$

  3. L is context free but not regular

  4. L is not context free

$\endgroup$
  • 2
    $\begingroup$ Because $L$ it is regular and it is not $00^*$ but $00(00)^*$, so this refers to $L$ being a different language, not to deny that $0^+$ is regular? $\endgroup$ – Evil Oct 12 '17 at 14:57
  • 1
    $\begingroup$ @Evil My bad, english is not my native language. $\endgroup$ – Sumeet Oct 12 '17 at 15:04
  • $\begingroup$ Please give a reference for the problem you quote. $\endgroup$ – Raphael Oct 12 '17 at 16:25
5
$\begingroup$

The statement (2) is ambiguous. It could mean either $$ L \text{ is regular but } L \text{ is not equal to } 0^+ \tag{1} $$ Or it could mean, $$ L \text{ is regular but } 0^+ \text{ is not regular} \tag{2} $$ (1) is true and (2) is false. The authors of the question intended it to mean (1). But you thought that the meaning was (2), so you were confused.

$\endgroup$

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.