Theory Of Computation (2160704)

Union Rule

• If L₁ and L₂ are context - free languages, then the languages L₁ U L₂ is also CFL(context - free languages).

• Union : G_u = (V_u, Σ, S_u, P_u)

  • A grammar G_u = (V_u, Σ, S_u, P_u) generating L₁ U L₂.
  • First we rename the element of V₂ if necessary so that V₁ n V₂= ∅
  • V_u= V₁ U V₂ U {S_u}
  • Where S_u is a new symbol not in V₁ or V₂.
  • Then we let P_u= P₁ U P₂ U { S_u --> S₁ | S₂ }
  • On the other hand, if x is derivable from S_u in G_u, the first step in any derivation must be
  • S_u -> S₁ or S_u -> S₂
  • In the first case, all subsequent productions used must be productions in G₁, because no variables in V₂ are involved, and thus x ∈ L₁; in the second case, x ∈ L₂. Therefore,
  • L(G_u) ⊆ L₁ U L₂

Concatenation

• If L₁ and L₂ are context - free languages, then the languages L₁L₂ is also CFL(context - free languages).

• Concatenation G_c= (V_c, Σ, S_c, P_c)

  • A grammar G_c= (V_c, Σ, S_c, P_c) generating L₁L₂ .
  • Again we relabeled variables if necessary so that V₁ ∩ V₂ = ∅ and
  • define V_c = V₁ ∪ V₂ ∪ {S_c}
  • This time we let
  • P_c= P₁ ∪ P₂ ∪ { S_c -> S₁S₂ }
  • If x ∈ L₁L₂ then x = x₁x₂ , where x_i ∈ L_i for each i. we may then derive x in G_c as follows:
  • S_c -> S₁ S₂ -> *x₁ S₂ -> * x₁x₂ = x
  • First step in the derivation must be Sc -> S₁S₂ Where the second step is the derivation of x₁ in G₁ and the third step is the derivation of x₂ in G₂. So x ∈ L₁L₂