Left quotient

From Infogalactic: the planetary knowledge core
Jump to: navigation, search

Lua error in package.lua at line 80: module 'strict' not found.

If L_1 and L_2 are formal languages, then the left quotient of L_1 with L_2 is the language consisting of strings w such that xw is in L_2 for some string x in L_1. In symbols, we write:

L_1 \backslash L_2 = \{w \ | \ \exists x ((x \in L_1)  \land (xw \in L_2))\}

You can regard the left quotient as the set of postfixes that complete words from L_2, such that the resulting word is in L_1.

For more details, see right quotient.