patternModerate
When is the concatenation of two regular languages unambiguous?
Viewed 0 times
thelanguagesregularunambiguoustwowhenconcatenation
Problem
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?
Is there an algorithm for deciding whether the concatenation of two regular languages is unambiguous?
Solution
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.
Context
StackExchange Computer Science Q#44844, answer score: 10
Revisions (0)
No revisions yet.