Let $L$ be the language over the alphabet $\{0, 1, 2, 3, (,), +, -, *, /\}$, $L$ is the set of operations with correctly formatted natural numbers. A single number is considered to belong to $L$.

2 - - 3 is an incorrect expression, 2 + 3 is correct, 2 + (-3) is correct. Is it possible to write a regular expression for this language? If not, why?

I think that it is not possible to write a regular expression for this language, because of the operator / we cannot write 2 / 0 for example and are more than a finite number combinations to make this possible. Is it correct?

  • $\begingroup$ Can you define the language $L$ in more detail? $\endgroup$ – Yuval Filmus Oct 13 '19 at 10:40
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael Oct 13 '19 at 11:00
  • $\begingroup$ It is not possible to be 2 * * 3 or 2 + + 5 for example. So it is not correct to repeat the some operator more than one $\endgroup$ – Daniel Oct 13 '19 at 13:35
  • $\begingroup$ It's impossible to write a Regex for your problem since your language $L$ is a Context-Free Language, and thats without checking for edge cases like divide-by-zero. $\endgroup$ – RandomPerfectHashFunction Oct 13 '19 at 14:14

You haven't defined your language, but presumably $$ L \cap [^*0+0](+0])^* = \{ [^n[0+0](+0])^n : n \geq 0 \}, $$ where I replaced parentheses with square brackets. The latter language is essentially $\{a^nb^n : n \ge 0 \}$ in disguise, and so isn't regular. It follows that $L$ isn't regular as well.


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.