HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
computer science Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, the right quotient (or simply quotient) of a
language Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of met ...
L_1 with respect to language L_2 is the language consisting of
strings String or strings may refer to: *String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects Arts, entertainment, and media Films * ''Strings'' (1991 film), a Canadian anim ...
''w'' such that ''wx'' is in L_1 for some string ''x'' in Formally: L_1 / L_2 = \ In other words, we take all the strings in L_1 that have a suffix in L_2, and remove this suffix. 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 L_1 = \ 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 = \ and L_2 = \. 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^ or a^n b^n c^; and L_1 / L_2 can be written as \.


Properties

Some common closure properties of the quotient operation include: * The quotient of a
regular language In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
with any other language is regular. * The quotient of a
context free language In formal language theory, a context-free language (CFL) is a language generated by a context-free grammar (CFG). Context-free languages have many applications in programming languages, in particular, most arithmetic expressions are generated by ...
with a regular language is context free. * The quotient of two context free languages can be any
recursively enumerable In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if: *There is an algorithm such that the ...
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 In theoretical computer science, in particular in formal language theory, the Brzozowski derivative u^S of a set S of strings and a string u is the set of all strings obtainable from a string in S by cutting off the prefix u, as illustrated in th ...


References

{{reflist Formal languages