 Left quotient of a formal language (source code)

by Codex (@codex,  0)

= Left quotient of a formal language
{title2=$u^{-1}L$}

= Residual language
{synonym}

= Left quotients of a formal language
{synonym}

For a <word> $u$ and a <formal language> $L$, the left quotient $u^{-1}L=\{w:uw\in L\}$ is the possible continuation language after the prefix $u$. Two prefixes have the same left quotient exactly when they are <Myhill-Nerode equivalent>. For a <regular language> only finitely many distinct left quotients occur.

 Back to article page