Question

Problem 4. Convert RE to CFG

We saw in class how to construct CFGs for U, *, and ^o operations for existing CFL's. We also saw how to construct CFG's for regular expressions empty-set, e, and c (where c is some member of S).

a) Using these constructions, create CFG for the RE R = x ((yx)* U y). This is an algorithm for converting any RE to a CFG with start variable S₀. It works as follows:

1. create an expression tree for R and number the nodes in your tree; number the root with 0
2. create CFGs for each leaf node, with the start state S_k, where k is the number of that node
3. go bottom up, building up from the simpler CFGs; continue naming your start variables with the S_k format

Don't worry that this algorithm creates a grammar that is not as simple (small) as can be.

b)  Given the existence of this algorithm, prove that all regular languages are context free.

Note: Proof must proceed by structural induction on regular expressions, very similar to how we proved that for every regular expression, there is an equivalent NFA.

Answer 1

a) S₀ --> xS₁

S₁   --> S₂ | S₃

S₂ --> S₄ S₂ | ε

S₃  --> y

S₄ --> yx | ε

  

b) Let R be a Regular Expression. Therefore, there exists a Definite Finite Automata N with set of Vertices V, set of States Q. As it is DFA, for every state, there exists another state to which machine goes next. For every accepting state, add a rule that current states approaches empty or epsilon. Finally, make the starting variable approaching the initial state. Hence all regular languages are context free.

.>>