1
$\begingroup$

How can I convert the regular expression (ab*)*b to a context-free grammar?

When I look for examples I keep seeing plus signs in the expression but I don’t have any. Is that just a different way of writing it?

$\endgroup$
2

1 Answer 1

3
$\begingroup$

There is a simple algorithm to convert regular expressions to context-free grammars. It goes as follows.

Base cases:

  • $\emptyset$ corresponds to the empty grammar.
  • $\epsilon$ corresponds to the grammar $S \to \epsilon$.
  • $\sigma$ (where $\sigma \in \Sigma$) corresponds to the grammar $S \to \sigma$.

Inductive cases:

  • $r = r_1 + r_2$. Given CFGs for $r_1,r_2$ with disjoint nonterminals and starting symbols $S_1,S_2$, add rules $S \to S_1 \mid S_2$ and make $S$ the new starting symbols.
  • $r = r_1r_2$. Same, adding the rule $S \to S_1 S_2$ instead.
  • $r = r_1{}^*$. Same, adding the rules $S \to S S_1 \mid \epsilon$ instead.
$\endgroup$

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.