## 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