Quotient of a formal language

From Wikipedia, the free encyclopedia
  (Redirected from Right quotient)
Jump to: navigation, search

In mathematics and computer science, the right quotient (or simply quotient) of a formal language with a formal language is the language consisting of strings w such that wx is in for some string x in .[1] In symbols, we write:

In other words, each string in is the prefix of a string in , with the remainder of the word being a string in .

Similarly, the left quotient of with is the language consisting of strings w such that xw is in for some string x in . In symbols, we write:

The left quotient can be regarded as the set of postfixes that complete words from , such that the resulting word is in .

Example[edit]

Consider

and

.

Now, if we insert a divider into the middle of an element of , the part on the right is in 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 or ; and can be written as

.

Properties[edit]

Some common closure properties of the right quotient 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.

References[edit]

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