Quotient of a formal language
In mathematics and computer science, the right quotient (or simply quotient) of a language with respect to language is the language consisting of strings such that is in for some string in {{nowrap|,}} where and are defined on the same alphabet {{nowrap|.}} Formally:{{cite book |last=Pin |first=J-É. |author-link=Jean-Éric Pin |translator-last=Howie |translator-first=A. |date=1986 |title=Varieties of Formal Languages |location=New York |publisher=Plenum Press |isbn=0306422948 |pages=14}}{{cite book |last1=Linz |first1=Peter |last2=Rodger |first2=Susan H. |author-link2=Susan H. Rodger |name-list-style=amp |date=2023 |title=An Introduction to Formal Languages and Automata |edition=Seventh |location=Burlington, MA |publisher=Jones & Bartlett Learning |isbn=978-1284231601 |pages=112–117}} ([https://books.google.com/books?id=hsxDiWvVdBcC&dq=right+quotient+automata&pg=PA104 Fifth ed.] at Google Books)
where is the Kleene star on , is the language formed by concatenating with each element of {{nowrap|,}} and is the empty set.
In other words, for all strings in that have a suffix in , the suffix (right part of the string) is removed.
Similarly, the left quotient of with respect to is the language consisting of strings such that is in for some string in . Formally:
In other words, for all strings in that have a prefix in , the prefix (left part of the string) is removed.
Note that the operands of are in reverse order, so that preceeds .
The right and left quotients of with respect to may also be written as and respectively.{{cite book |last=Simovici |first=Dan A. |date=2024 |title=Introduction to the Theory of Formal Languages |location=Singapore |publisher=World Scientific |isbn=978-9811294013 |doi=10.1142/13862 |pages=11–12}}
Example
Consider
and
If an element of is split into two parts, then the right part will be in if and only if the split occurs somewhere after the final {{nowrap|.}} Assuming this is the case, if the split occurs before the first then and {{nowrap|}}, otherwise and {{nowrap|.}} For instance:
where is the empty string.
Thus, the left part will be either or {{nowrap|}} {{nowrap|),}} and can be written as:
Basic properties
=Example proof=
As an example, the third property is proved as follows:
If {{nowrap|,}} there exists such that {{no wrap|.}} Since then and {{nowrap|,}} it must be that {{nowrap|.}} Conversely, let and {{nowrap|,}} then there exists such that and (given {{nowrap|,}} if then may differ). Now and only if {{nowrap|,}} hence {{nowrap|.}}
For instance, let {{nowrap|.}}
Then {{no wrap|}}, hence {{nowrap|.}}
Also and {{nowrap|}}, hence {{nowrap|.}}
Relationship between right and left quotients
The right and left quotients of languages and are related through the language reversals and by the equalities:
=Proof=
To prove the first equality, let {{nowrap|.}} Then there exists such that {{nowrap|.}} Therefore, there must exist such that {{nowrap|,}} hence by definition {{nowrap|.}} It follows that {{nowrap|,}} and so {{nowrap|.}}
The second equality is proved in a similar manner.
Other 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
{{reflist}}