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
The blog provides study material for Computer Science(CS) aspirants. Mostly says "material nahi milta, padhun kahan se.", I think If you can not find content on the Internet, then you are not a CS student. Dedicated to (Prof. Rakesh Kumar, DCSA, K.U.Kurukshetra, HARYANA, INDIA)- "Ek teacher ka bahut jyada padhna, bahut jyada jaroori hota hai."
Monday, 24 June 2013
CFL closure properties
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment