# Arithmetic operators and regex

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?

• Can you define the language $L$ in more detail? – Yuval Filmus Oct 13 at 10:40
• 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! – Raphael Oct 13 at 11:00
• 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 – Daniel Oct 13 at 13:35
• 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. – RandomPerfectHashFunction Oct 13 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.