|Looking for references on regular language decomposition email@example.com (1995-06-24)|
|Re: Looking for references on regular language decomposition firstname.lastname@example.org (1995-06-28)|
|From:||email@example.com (Mark A Biggar)|
|Organization:||Loral Western Development Labs|
|Date:||Wed, 28 Jun 1995 17:09:11 GMT|
firstname.lastname@example.org (Reid M. Pinchback) writes:
>I'm looking for references for theorems and algorithms for the
>- Let L1 ... Ln be regular languages. By "regular language" I mean
>exactly the same thing as you get in any introductory compilers
>- 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.
Return to the
Search the comp.compilers archives again.