I have the following regex that I'm trying to convert to a CFG: e|a(,a)* (e representing the empty state). Basically I want to match a comma-separated list (without a leading or trailing comma) or nothing at all. Here are some of my attempts:

S = A
A = e | a | a , A

This doesn't work, it matches ,a (leading comma).

S = A | B
A = e
B = a C
C = , C | a | e

This doesn't work either, it matches a, and aa (trailing and missing comma).

Is my regex even representable as a CFG?

Thanks in advance


1 Answer 1


At the heart of your regex is an alternation {$\alpha|\beta$), which means that the regex matches $\alpha$ or $\beta$. That's how you should write the CFG: $$\begin{align}S\to&\;\alpha\\ |&\;\beta \end{align}$$ Here, $\alpha$ is $\varepsilon$ and $\beta$ is the subexpression $a(,a)^*$, for which we'll define the non-terminal $A$.

It's easy to see what $A$ is: it starts with an $a$ and can be extended arbitrarily with $, a$: $$\begin{align}S\to&\;\varepsilon\\ |&\;A\\ A\to&\;a\\ |&\;A\;,a \end{align}$$

  • $\begingroup$ thank you so much! $\endgroup$
    – user156830
    Jan 14 at 9:03

Your Answer

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

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