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 that you have read and understand our privacy policy and code of conduct.