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 1


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)

  • $\begingroup$ 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 -> ++++ $\endgroup$
    – Guest
    Feb 28, 2021 at 0:01
  • $\begingroup$ You are right. I accidentally added the production $B\rightarrow \epsilon$ instead of $B\rightarrow 0\space |\space 1$ $\endgroup$
    – nir shahar
    Feb 28, 2021 at 0:03
  • $\begingroup$ 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? $\endgroup$
    – Guest
    Feb 28, 2021 at 0:15
  • 1
    $\begingroup$ You could do this if you don't want unnecessary parenthesis. $\endgroup$
    – nir shahar
    Feb 28, 2021 at 0:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.