HiveBrain v1.2.0
Get Started
← Back to all entries
patternModerate

When is the concatenation of two regular languages unambiguous?

Submitted by: @import:stackexchange-cs··
0
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?

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.