Quotient of a formal language explained

L _{1} with respect to language L _{2} is the language consisting of strings w such that wx is in L _{1} for some string x in ^[1] Formally:$$L\_1\; /\; L\_2\; =\; \backslash$$

In other words, for all the strings in

L _{1} that have a suffix in L _{2} , the suffix is removed.

Similarly, the left quotient of

L _{1} with respect to L _{2} is the language consisting of strings w such that xw is in L _{1} for some string x in L _{2} . Formally:$$L\_2\; \backslash backslash\; L\_1\; =\; \backslash$$

In other words, we take all the strings in

L _{1} that have a prefix in L _{2} , and remove this prefix.

Note that the operands of

\backslash are in reverse order: the first operand is L _{2} and L _{1} is second.

Example

Consider$$L\_1\; =\; \backslash$$and$$L\_2\; =\; \backslash .$$

Now, if we insert a divider into an element of

L _{1} , the part on the right is in L _{2} only if the divider is placed adjacent to a b (in which case i ≤ n and j = n) or adjacent to a c (in which case i = 0 and j ≤ n). The part on the left, therefore, will be either a ^{n} b ^{n-i} or a ^{n} b ^{n} c ^{n-j} ; and L _{1} / L _{2} can be written as$$\backslash .$$

Properties

Some common closure properties of the quotient operation include:

• The quotient of a regular language with any other language is regular.
• The quotient of a context free language with a regular language is context free.
• The quotient of two context free languages can be any recursively enumerable language.
• The quotient of two recursively enumerable languages is recursively enumerable.

These closure properties hold for both left and right quotients.

See also

• Brzozowski derivative

Notes and References

1. Book: Linz. Peter. An Introduction to Formal Languages and Automata. 2011. Jones & Bartlett Publishers. 9781449615529. 104–108. 7 July 2014.