Monday, 24 June 2013

CFL closure properties

Given two CFG's  G1 = (V1, T1, P1, S1) for language L1(G1)
                   G2 = (V2, T2, P2, S2) for language L2(G2)

  Rename variables until V1 intersect V2 is Phi.

  We can easily get CFG's for the following languages:

  L1 union L2 = L3(G3)
     G3 = (V1 union V2 union {S3}, T1 union T2, P1+P2+P3, S3)
           S3 -> S1 | S2


  L1 concatenated L2 = L4(G4)
     G4 = (V1 union V2 union {S4}, T1 union T2, P1+P2+P4, S4)
           S4 -> S1S2


  L1 star = L5(G5)
     G5 = (V1 union V2 union {S5}, T1 union T2, P1+P2+P5, S5)
           S5 -> S5S1 | epsilon

  L2 substituted for terminal "a" in L1 = L6(G6)
     G6 = (V1 union V2, T1-{a} union T2, P6+P2, S1)
           P6 is P1 with every occurrence of "a" replaced with S2.

  Notice that L1 intersect L2 may not be a CFG.

                   i i j               i j i
     Example: L1={a b c  | i,j>0} L2={a b c  | i,j>0} are CFG's

                             i i i
     but L1 intersect L2 = {a b c  | i>0} which is not a CFG.

  The complement of L1 may not be a CFG.

  The difference of two CFG's may not be a CFG.

  The intersection of a Context Free Language with a Regular Language
  is a Context Free Language.

  As a supplement, the following shows how to take a CFG and possibly
  use  'yacc' or 'bison' to build a parser for the grammar.

  The steps are to create a file  xxx.y  that includes the grammar,
  and a file that is a main program that runs the parser.

A grammar that may be of more interest is a grammar for a calculator.
Simple statement such as  
  a=2
  b=3
  a+b
that prints the answer 5 can be coded as a CFG.

You should get the result 5 printed. See the grammar to find out what
other operations are available