Science Fair Project Encyclopedia

Science Fair Project Encyclopedia Contents Page

Right quotient

If $L 1$ and $L 2$ are formal languages, then the right quotient of $L 1$ with $L 2$ is the language consisting of strings w such that wx is in $L 1$ for some string x in $L 2$ . In symbols, we write:

$L_1 / L_2 = \{w \ | \ \ \exists x \in L_2 \ \ : \ \ wx \in L_1\}$

Some common closure properties of 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 is context sensitive.
The quotient of a context sensitive language and any other language could be anything, recursively enumerable or nonrecursively enumerable .

There is a related notion of left quotient, which keeps the postfixes of $L 1$ without the prefixes in $L 2$ . Sometimes, though, "right quotient" is written simply as "quotient". The above closure properties hold for both left and right quotients.

Science Fair Project Encyclopedia Contents Page

12-03-2008 10:22:39
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details

All Science Fair Projects

Science Fair Project Encyclopedia for Schools!

Science Fair Project Encyclopedia

Right quotient