16
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Gah, this is totally a freshman CS problem, isn't it? Honestly, I haven't tried much; I was hoping that there's an established algorithm for this somewhere in the literature and I wouldn't have to go reinventing the wheel. I'm writing software over here; I've only taken a couple of CS courses (several years ago) so I'm basically starting from Wikipedia. I know nobody likes someone who doesn't want to work for their answer, so if there's a textbook or a paper or something that you could point me at instead of just handing me an algorithm, that would be helpful! Thanks! $\endgroup$ – rstern Jul 29 '15 at 20:41
  • $\begingroup$ I added this as a comment because, well its relatively off topic, but perhaps can lead you to some help. The Unicode Consortium has a few processes for determining the commonality between languages. I have read a very informative link on their site but for the life of me could not find it today to make this an answer instead. If you have time to research this here is their FAQ page unicode.org/faq $\endgroup$ – htm11h Jul 30 '15 at 15:21
10
$\begingroup$

Hint: Given DFAs for $A$ and $B$, construct an NFA which accepts words in $AB$ having at least two different decompositions. The NFA keeps track of two copies of the standard NFA for $AB$ (formed by joining DFAs for $A$ and $B$ with $\epsilon$ transitions), ensuring that the switch from $A$ to $B$ happens at two different points.

$\endgroup$
  • $\begingroup$ Thanks for the hint! So if I understand, I can construct an NFA for ambiguous words in $AB$ and then test that automaton for emptiness. The tricky part seems to be "ensuring that the switch from $A$ to $B$ happens at two different points". I'm not sure how to do that other than taking the cross product (?) of two $AB$ DFAs and deleting all of the ($A$-terminal, $A$-terminal) product states—I'm handwaving, I'm worried that the transition from $AB$ NFA to $AB$ DFA would screw with the idea of $A$-terminal. Sounds, um, inefficient though; is there a known algorithm suitable for software? $\endgroup$ – rstern Jul 29 '15 at 20:34
  • $\begingroup$ Yes, it doesn't sound too efficient, though there is always the option of doing it in a smart way. I'm not aware of any specific algorithm for this problem, but one might exist. $\endgroup$ – Yuval Filmus Jul 29 '15 at 20:36
7
$\begingroup$

Updated (thanks to Yuval Filmus).

Given two languages $X$ and $Y$ of $A^*$, let \begin{align} X^{-1}Y &= \{u \in A^* \mid \text{there exists $x \in X$ such that $xu \in Y$} \} \\ YX^{-1} &= \{u \in A^* \mid \text{there exists $x \in X$ such that $ux \in Y$} \} \end{align} I claim that $XY$ is unambiguous if and only if the language $X^{-1}X \cap YY^{-1} \cap A^+$ is empty.

Proof. Suppose that $XY$ is ambiguous. Then there exists a word $u$ which has two decompositions over $XY$, say $u = x_1y_2 = x_2y_1$, where $x_1, x_2 \in X$ and $y_1, y_2 \in Y$. Without loss of generality, we may assume that $x_1$ is a prefix of $x_2$, that is, $x_2 = x_1z$ for some $z \in A^+$. It follows that $u = x_1y_2 = x_1zy_1$, whence $y_2 = zy_1$. Thus $z \in X^{-1}X \cap YY^{-1}$.

Suppose now that $X^{-1}X \cap YY^{-1}$ contains some nonempty word $z$. Then there exist $x_1, x_2 \in X$ and $y_1, y_2 \in Y$ such that $x_2 = x_1z$ and $y_2 = zy_1$. It follows that $x_2y_1 = x_1zy_1 = x_1y_2$ and hence the product $XY$ is ambiguous.

If $X$ and $Y$ are regular, then both $X^{-1}X$ and $YY^{-1}$ are regular and thus $X^{-1}X \cap YY^{-1}$ is also regular (see Yuval's answer for an automaton accepting this language).

$\endgroup$
  • $\begingroup$ What if $z$ is the empty word? $\endgroup$ – Yuval Filmus Jul 31 '15 at 12:42
  • $\begingroup$ Ooops. I update. $\endgroup$ – J.-E. Pin Jul 31 '15 at 12:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.