Thu, 12 Aug 2010 18:26:46 -0700 (PDT)

Related articles |
---|

question about "merging" two context-free languages (CFL) tonywinslow1986@gmail.com (Tony) (2010-08-12) |

Re: question about "merging" two context-free languages (CFL) gene.ressler@gmail.com (Gene) (2010-08-14) |

From: | Tony <tonywinslow1986@gmail.com> |

Newsgroups: | comp.compilers,comp.theory |

Date: | Thu, 12 Aug 2010 18:26:46 -0700 (PDT) |

Organization: | Compilers Central |

Keywords: | parse, theory, question |

Posted-Date: | 12 Aug 2010 22:43:46 EDT |

Hi,

Suppose we have two context-free languages L1 and L2, and they have

disjoint alphabet set A1 and A2 (A1 \intersection A2 = \emptyset). Is

it possible to "merge" L1 and L2 into a new context-free language L

such that

1) the alphabet set A of L is A1 \union A2

2) a sequence of letters W (subset of A*) is a valid word in L if

and only if the longest subsequences W1 and W2 of W satisfy the

following conditions:

a) W1 (subset of A1*) is a valid word in L1

b) W2 (subset of A2*) is a valid word in L2

Example. A1={a, b}, A2={c, d}, L1=a L1 b | \epsilon; L2=c L2 d |

\epsilon. For the sequence "acbdca", W1 would be "abc", and W2 would

be "cdc". The sequence "acbd" would be a valid word in the new

language L since the subsequences W1="ab" and W2="cd" are valid in L1

and L2, respectively.

Thanks,

Tony

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.