Wed, 28 Jun 1995 17:09:11 GMT

Related articles |
---|

Looking for references on regular language decomposition reidmp@whirlwind.mit.edu (1995-06-24) |

Re: Looking for references on regular language decomposition mab@wdl.loral.com (1995-06-28) |

Newsgroups: | sci.math,comp.theory,comp.compilers |

From: | mab@wdl.loral.com (Mark A Biggar) |

Keywords: | theory |

Organization: | Loral Western Development Labs |

References: | 95-06-056 |

Date: | Wed, 28 Jun 1995 17:09:11 GMT |

reidmp@whirlwind.mit.edu (Reid M. Pinchback) writes:

*>I'm looking for references for theorems and algorithms for the*

*>following problem.*

*>- Let L1 ... Ln be regular languages. By "regular language" I mean*

*>exactly the same thing as you get in any introductory compilers*

*>course.*

*>- Let L be the language consisting of strings of L1 ... Ln*

*> concatenated in any order.*

*> In other words, L = ( L1 | ... | Ln )* where "|" signifies choice and "*" is*

*> star closure (ie: catenation 0 or more times)*

*>Here is my question. What theorems are available that specify when*

*>we can determine a *unique* decomposition of a string of L into*

*>substrings from L1 ... Ln. In other words, when can you uniquely*

*>parse a string of L so that you *know* which sublanguage each*

*>substring is from.*

*>Another variation on this is to answer the same question where the*

*>languages L1 ... Ln are described by regular grammars.*

I believe that this problem is equivalent to the Post Correspondence Problem,

which is undecidable in general.

--

Mark Biggar

mab@wdl.loral.com

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.