I'm currently in need of the inverse operation of the concatenation of 2 regular languages.

Formally, for 3 regular languages $A,B,C$ such that $A \cdot B = C$, only $A$ and $C$ are known, and $B$ is the smallest language that fulfills the equation (which implies $\forall w \in B: A \cdot (B \setminus \{w\}) \subset C$).

The smallest-language requirement is necessary for my practical application, but I believe it's also necessary to make $B$ unique.

Special cases:

  • $C = \varnothing \implies B = \varnothing$
  • $A = C \neq \varnothing \implies B = \{\epsilon\}$
  • $\epsilon \in A \implies B \subseteq C$


  1. Whether the left or right operant is unknown doesn't matter. By reversing both side of the equation, we get $B^R \cdot A^R = C^R$. So a solution that can find $A$ can also find $B$ and vise versa.
  2. $B$ is trivially unique for $|B|<2$.

Open questions:

  1. Is $B$ unique in general? (I believe it is.)
  2. Is $B$ a regular language?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.