Question

5 Regular => Context-Free

Give a proof by induction on regular expressions that:

For any language A, if A is regular, then A is also context-free.

You may assume that the statements from the previous Closure under Context-Free Languages problem are proved.

Answer 1

Regular Languages are Context-Free:

The following inductive argument proves that every regular language is also a context-free

language. Let L be an arbitrary regular language, encoded by some regular expression R. Assume

that any regular expression simpler than R represents a context-free language. (“Assume no

smaller counterexample.”) We construct a context-free grammar for L as follows. There are

several cases to consider.

• Suppose L is empty. Then L is generated by the trivial grammar S → S.

• Suppose L = {w} for some string w ∈ Σ

∗

. Then L is generated by the grammar S → w.

• Suppose L is the union of some regular languages L1 and L2

. The inductive hypothesis

implies that L1 and L2 are context-free. Let G1 be a context-free language for L1 with

starting non-terminal S1

, and let G2 be a context-free language for L2 with starting non-

terminal S2

, where the non-terminal sets in G1 and G2 are disjoint. Then L = L1 ∪ L2

is

generated by the production rule S → S1

| S2

.

• Suppose L is the concatenation of some regular languages L1 and L2

. The inductive

hypothesis implies that L1 and L2 are context-free. Let G1 be a context-free language for

L1 with starting non-terminal S1

, and let G2 be a context-free language for L2 with starting

non-terminal S2

, where the non-terminal sets in G1 and G2 are disjoint. Then L = L1 L2

is

generated by the production rule S → S1S2

.

• Suppose L is the Kleene closure of some regular language L1

. The inductive hypothesis

implies that L1

is context-free. Let G1 be a context-free language for L1 with starting

non-terminal S1

. Then L = L

∗

1

is generated by the production rule S → " | S1S.

In every case, we have found a context-free grammar that generates L, which means L is Regular also

I hope this solution helps you give an upvote!!