Skip to main content
edited tags
Link
Raphael
  • 72.9k
  • 30
  • 181
  • 393
Tweeted twitter.com/#!/StackCompSci/status/626537283789959168
Source Link
rstern
  • 171
  • 5

When is the concatenation of two regular languages unambiguous?

Given languages $A$ and $B$, let's say that their concatenation $AB$ is unambiguous if for all words $w \in AB$, there is exactly one decomposition $w = ab$ with $a \in A$ and $b \in B$, and ambiguous otherwise. (I don't know if there's an established term for this property—hard thing to search for!) As a trivial example, the concatenation of $\{\varepsilon, \mathrm{a}\}$ with itself is ambiguous ($w = \mathrm{a} = \varepsilon \mathrm{a} = \mathrm{a} \varepsilon$), but the concatenation of $\{\mathrm{a}\}$ with itself is unambiguous.

Is there an algorithm for deciding whether the concatenation of two regular languages is unambiguous?