Content deleted Content added
→Right quotient: The subsection also covers left quotient, the heading now reflects this. |
→Right and left quotient: fmt (nowrap) |
||
Line 130:
:<math>\pi_\Sigma (L)=\{\pi_\Sigma(s)\ \vert\ s\in L \}</math>{{citation needed|date=August 2017}}
== Right and left quotient ==
The '''right quotient''' of a character ''a'' from a string ''s'' is the truncation of the character ''a'' in the string ''s'', from the right hand side. It is denoted as <math>s/a</math>. If the string does not have ''a'' on the right hand side, the result is the empty string. Thus:
<!---This definition deviates from Hopcroft.Ullman.1979, as remarked below. I guess the former doesn't have widespread use, if it has a source at all.--->
: <math>(sa)/ b = \begin{cases} ▼
▲:<math>(sa)/ b = \begin{cases}
s & \mbox{if } a=b \\
\varepsilon & \mbox{if } a \ne b
Line 140 ⟶ 139:
The quotient of the empty string may be taken:
: <math>\varepsilon / a = \varepsilon</math>▼
▲:<math>\varepsilon / a = \varepsilon</math>
Similarly, given a subset <math>S\subset M</math> of a monoid <math>M</math>, one may define the quotient subset as
: <math>S/a=\{s\in M\ \vert\ sa\in S\}</math>▼
▲:<math>S/a=\{s\in M\ \vert\ sa\in S\}</math>
'''Left quotients''' may be defined similarly, with operations taking place on the left of a string.{{citation needed|date=August 2017}}
Hopcroft and Ullman (1979) define the quotient ''L''<sub>1</sub>/''L''<sub>2</sub> of the languages ''L''<sub>1</sub> and ''L''<sub>2</sub> over the same alphabet as {{nowrap|1=''L''<sub>1</sub>/''L''<sub>2</sub> = {{mset| ''s''
This is not a generalization of the above definition, since, for a string ''s'' and distinct characters ''a'', ''b'', Hopcroft's and Ullman's definition implies {{nowrap||{{mset|''sa''}} / {{mset|''b''}}}} yielding {{mset|}}, rather than {{mset| ε }}.
The left quotient (when defined similar to Hopcroft and Ullman 1979) of a singleton language ''L''<sub>1</sub> and an arbitrary language ''L''<sub>2</sub> is known as [[Brzozowski derivative]]; if ''L''<sub>2</sub> is represented by a [[regular expression]], so can be the left quotient.<ref>{{cite journal| author=Janusz A. Brzozowski| authorlink=Janusz Brzozowski (computer scientist)|title=Derivatives of Regular Expressions| journal=J ACM| year=1964| volume=11| issue=4| pages=481–494| doi=10.1145/321239.321249| s2cid=14126942}}</ref>
| |||