# CFG of all regular expressions over a binary alphabet

I'm working on creating a rather difficult CFG and I am getting stuck on finishing it. The CFG in question is meant to contain all valid regular expressions using the alphabet {0, 1, (, ), *, +, e} (e for epsilon).

Some examples I know that should be accepted are things like:

• e
• 0
• 01
• 1010
• 0*1*0*1*
• 0*11+(10)*+(e+1*0*)
• ((100*)*(10*)*)*

While things such as these would be rejected:

• ee
• )(e+1*)*
• (10)*++(

et cetera

I've been building up case by case and I have this rather ugly looking CFG that prevents most incorrect cases, but it does not come close to getting all the correct ones

S → (N) | M+M | N | (N)*

M → 0N | 1N | 0N | 1N | (N) | (N)* | M+M | e

N → 0N | 1N | 0N | 1N | ɛ

Apologies if this has been asked before, I tried searching everywhere here and on Google and I was not able to find someone else trying to create the same or similar CFG, but if this is a repeat I'd appreciate being pointed to the original!!

If helpful, I've been using this tool to test my CFG: https://web.stanford.edu/class/archive/cs/cs103/cs103.1156/tools/cfg/

## 1 Answer

You are quite close to the solution. We will use a few variables, each corresponding (intuitively) to some other "thing". Specifically, we will use the variables $$S,E,A,B$$.

$$S$$ is the starting variable. $$E$$ is a variable that will produce a valid regular expression (its called $$E$$ as short for "expression"). $$A$$ will be some valid string over the alphabet $$\{0, 1\}$$, and $$B$$ will be a non-empty string over that same alphabet.

The CFG will now be:

$$S\rightarrow E$$

$$E \rightarrow (E)(E) \space | \space E+E \space|\space E^* \space | \space (E) \space|\space A$$

$$A\rightarrow B\space |\space e$$

$$B \rightarrow 0B \space | \space 1B \space | \space 0 \space | \space 1$$

I hope this CFG is what you are looking for! (I don't know if it is, since you didn't state the definition of the syntax of a regular expression using this alphabet, so I have only tried to go by the examples)

• Hey! I appreciate the help but unfortunately this can produce invalid regular expressions. E.g. S -> E -> E+E -> E+E+E+E -> A+A+A+A -> B+B+B+B -> ++++ – Guest Feb 28 at 0:01
• You are right. I accidentally added the production $B\rightarrow \epsilon$ instead of $B\rightarrow 0\space |\space 1$ – nir shahar Feb 28 at 0:03
• I believe B needs to be expanded to: $B \rightarrow 0B \space | \space 1B \space | \space 0 \space | \space 1 \space | \space 0^*B \space | \space 1^*B$ to account for cases such as 0*11, what do you think? – Guest Feb 28 at 0:15
• You could do this if you don't want unnecessary parenthesis. – nir shahar Feb 28 at 0:23