I have created a context-free grammar

$$ \begin{align*} &S \to S_1 \mid S_2 \\ &S_1 \to aS_3bS_4 \mid \epsilon \\ &S_2 \to bS_4 \\ &S_3 \to aS_3 \mid \epsilon \\ &S_4 \to aS_4 \mid bS_4 \mid \epsilon \end{align*} $$

for this regular expression

$ (aa^*b(a \cup b)^*) \cup (b(a \cup b)^*) $

Is the grammar correct or am I missing a certain route?


1 Answer 1


One way to check whether you have got correct grammar is to use plain English or regular expression to characterize each non-terminals, starting from the more basic blocks.

$$S_4 \to aS_4 \mid bS_4 \mid \epsilon$$ This rule says $S_4$ is the words any words made up by zero or more $a$'s and $b$'s or, what is equivalent, $(a\cup b)^*$.

$$S_3 \to aS_3 \mid \epsilon$$ This rule says $S_3$ is the words any words made up by zero or more $a$'s or what is equivalent, $a^*$.

$$S_2 \to bS_4$$ This rule says $S_2$ is all words that are $b$ followed by zero or more $a$'s or $b$'s or what is equivalent $a(a\cup b)^*$.

$$S_1 \to aS_3bS_4 \mid \epsilon$$ These two rules says $S_1$ is $aa^*b(a\cup b)^*$ or the empty string.

$$S \to S_1 \mid S_2$$ This rule says $S$ is $aa^*b(a\cup b)^*$ or the empty string or $a(a\cup b)^*$.

The given regular expression for $S$ is $$ (aa^*b(a \cup b)^*) \cup (b(a \cup b)^*). $$ Can you see the difference between the given regular expression and the above description of $S$? Yes, the extra empty string. That is the single difference.

If the given regular expression is more complex, we might need to design some algorithm and implement it in some programming language. For the simple ones like this, the above step by step analysis should be enough. Be careful, of course.


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.