I am stuck on a problem involving PDA's and CFG's. The problem is as stated:

Give a CFG and a PDA for the language of regular expressions over the alphabet $\{a, b, c\}$. Give the formal tuple definition of each. You may use the shorthand for pushing a string in the state diagram of your PDA, but not in the tuple form. It will help if you expand out the shorthand in the state diagram. To avoid ambiguity, use the symbols $($, $)$, $λ$ for the language. The alphabet should be $\{a, b, c,(,), +, λ,∗ \}$. For brevity, you can define $δ$ by giving its output on the inputs that don’t return $∅$. Something like $δ(x_1) = y_1; δ(x_2) = y_2;$

My first attempt at it got me stuck after defining the Context Free Grammar and the PDA. I am having trouble understanding how this grammar could, for instance,

  • Derive $(a + b)^*(c + λ)a^*$

  • Make a PDA for this.

How can I make a PDA for this? How can I make a CFG for this?

  • $\begingroup$ I'm not sure what you're asking. If you've constructed a grammar, what's the problem with showing that your grammar produces the required string? And then there are standard algorithms for converting CFGs to PDAs. $\endgroup$ Nov 17, 2016 at 9:45
  • 1
    $\begingroup$ The analogous problem for arithmetic expressions is commonly presented in introductory texts. I suggest you find one and (slightly) modify it for regular expressions. $\endgroup$ Nov 17, 2016 at 14:52

1 Answer 1


Hint: Let us assume an alphabet $\Sigma$. Now, the following are regular expressions (at least according to some textbooks):

  • $a$ is a regular expression, if $a \in \Sigma$
  • $\emptyset$ is a regular expression
  • $r_1 \cup r_2$ is a regular expression, if $r_1$ and $r_2$ are regular expressions
  • $r_1 \circ r_2$ is a regular expression, if $r_1$ and $r_2$ are regular expressions
  • Nothing else is a regular expression.

How can you summarize these formation rules as a collection of context-free production rules where $r$ is a nonterminal?


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.