Question

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.

R is a regular expression if RR is:

1. a for some a∈alphabet Σ,

2. the empty string ε,

3. the empty set ∅,

4. R​1​​∪R​2​​, sometimes written R​1​​∣R​2​​, where R​1​​ and R​2​​ are regular expressions,

5. R​1​​∘R​2​​, sometimes written R​1​​R​2​​, where R​1​​ and R​2​​ are regular expressions,

6. R​1​∗​​, where R​1​​ is a regular expression.

Closure under Context-Free Languages

• union

• concatentation

• Kleene star

Answer 1

Hi,

All regular languages are context free languages .we can prove it by induction.

A context free languge can be defined as a language that are generated by context free grammers.It have some production rule.A regular language is a language that is expressed using regular expression.We can prove that all egular languaes are ontext free by proving that for eery regular languages there is a context free grammer exist.We know that regular languages are closed under union,concatenation and kleen star.We need to prove that htey are closed under context free grammer also.Let us consider:

• Union : If R1 and R2 are regular languages then R1 R2 is also regular.We need to prove that they are closed under context free language.For that we need to construct a grammer.Suppose P is a start symbol and it produces P->P1|P2,so P->P1 ,here P1 matches R1 and P->P2 and it matches R2 so we can write the rule as P->R1|R2.
• Concatination: If R1 and R2 are regular languages then R1R2 is also regular.We can create a production rule of concatination in context free grammer as P->P1P2.Here P1 matcher R1 in the regular language and P2 matches R2 in the regular language.So the production can be write as P->R1R2
• Kleenstar: If R1 is a regular language then R1* is also regular .Let P1 be generated by context free grammer and we can define P->P1P so that every word in P1* is generated by P and R1 matches P1 .So the production rule becomes P-> R1*.

Hence it is proved.

Thank you....