Recursive cases: Let A, B be arbitrary RegExps and Let C$_{A}$, C$_{B}$ be cfg(A) and cfg(B) where the properties of cfg can be defined as:
- cfg($\phi$) = the CFG with no productions
- cfg($\epsilon$) = the CFG with no productions
- cfg(a) = the CFG with just the prouction s $\to$ a for any a $\in$ $\sum$
- cfg(AB) = C$_{A}$, C$_{B}$, S$\to$S$_{A}$S$_{B}$
- cfg(A$\bigcup$B) = C$_{A}$, C$_{B}$, S$\to$S$_{A}$ | S$_{B}$
- cfg(A*) = C$_{A}$, S$\to\epsilon$ | S$_{A}$S$_{B}$
The goal: Prove that for any R $\in$ RegExp, the language accepted by R is a subset of the language accepted by cfg(R).
For my base cases, I think I should probably make A, B be empty sets... but where do I go from there? I'm still really confused about the structure of induction proofs and what my inductive hypothesis should be.