Algorithm: Union Input: G1 = (Σ1, NT
1,R1,S1)
G2 = (Σ2,NT
2,R2,S2), where NT1 ∩ NT2 = ∅Output: G = (Σ1 ∪ Σ2, NT
1 ∪NT
2 ∪ {$}, R1 ∪ R2 ∪ {($,S1),($,S2)}, $), where $ is a new symbol, i.e. $ ∉ NT1 ∪ NT2
Algorithm: Concatenation Input: G1 = (Σ1, NT
1,R1,S1)
G2 = (Σ2,NT
2,R2,S2), where NT1 ∩ NT2 = ∅Output: G = (Σ1 ∪ Σ2, NT
1 ∪NT
2 ∪ {$}, R1 ∪ R2 ∪ {($,S1S2)}, $), where $ is a new symbol, i.e. $ ∉ NT1 ∪ NT2
Since a grammar for ∅, {λ} and {a}, for any character a, is trivial, we have all the operations we need for regular expressions. Thus, we can start with a regular expression, build recursively build grammars for its subexpressions, and combine them with our algorithms. The resulting algorithm is a proof that any regular language can be defined by a context free grammar.
Algorithm: Kleene Star Input: G = (Σ, NT
,R,S)Output: G' = (Σ, NT
∪ {$}, R ∪ {($,S$),($,λ)}, $), where $ is a new symbol, i.e. $ ∉ NT