Misplaced Pages

Quotient of a formal language

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
(Redirected from Right quotient)

In mathematics and computer science, the right quotient (or simply quotient) of a language L 1 {\displaystyle L_{1}} with respect to language L 2 {\displaystyle L_{2}} is the language consisting of strings w such that wx is in L 1 {\displaystyle L_{1}} for some string x in L 2 {\displaystyle L_{2}} . Formally: L 1 / L 2 = { w ∈ Σ ∗ ∣ ∃ x ∈ L 2 :   w x ∈ L 1 } {\displaystyle L_{1}/L_{2}=\{w\in \Sigma ^{*}\mid \exists x\in L_{2}\colon \ wx\in L_{1}\}}

In other words, for all the strings in L 1 {\displaystyle L_{1}} that have a suffix in L 2 {\displaystyle L_{2}} , the suffix is removed.

Similarly, the left quotient of L 1 {\displaystyle L_{1}} with respect to L 2 {\displaystyle L_{2}} is the language consisting of strings w such that xw is in L 1 {\displaystyle L_{1}} for some string x in L 2 {\displaystyle L_{2}} . Formally: L 2 ∖ L 1 = { w ∈ Σ ∗ ∣ ∃ x ∈ L 2 :   x w ∈ L 1 } {\displaystyle L_{2}\backslash L_{1}=\{w\in \Sigma ^{*}\mid \exists x\in L_{2}\colon \ xw\in L_{1}\}}

In other words, we take all the strings in L 1 {\displaystyle L_{1}} that have a prefix in L 2 {\displaystyle L_{2}} , and remove this prefix.

Note that the operands of ∖ {\displaystyle \backslash } are in reverse order: the first operand is L 2 {\displaystyle L_{2}} and L 1 {\displaystyle L_{1}} is second.

Example

Consider L 1 = { a n b n c n ∣ n ≥ 0 } {\displaystyle L_{1}=\{a^{n}b^{n}c^{n}\mid n\geq 0\}} and L 2 = { b i c j ∣ i , j ≥ 0 } . {\displaystyle L_{2}=\{b^{i}c^{j}\mid i,j\geq 0\}.}

Now, if we insert a divider into an element of L 1 {\displaystyle L_{1}} , the part on the right is in L 2 {\displaystyle 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 {\displaystyle a^{n}b^{n-i}} or a n b n c n − j {\displaystyle a^{n}b^{n}c^{n-j}} ; and L 1 / L 2 {\displaystyle L_{1}/L_{2}} can be written as {   a p b q c r   ∣   p = q ≥ r     or     ( p ≥ q  and  r = 0 )   } . {\displaystyle \{\ a^{p}b^{q}c^{r}\ \mid \ p=q\geq r\ \ {\text{or}}\ \ (p\geq q{\text{ and }}r=0)\ \}.}

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

References

  1. Linz, Peter (2011). An Introduction to Formal Languages and Automata. Jones & Bartlett Publishers. pp. 104–108. ISBN 9781449615529. Retrieved 7 July 2014.
Category: