Content deleted Content added
m Dating maintenance tags: {{Cn}} |
→Right quotient: add and source H+U's (more general) def.; mention deviation to unsourced old version (suspected to be flawed/unusual) |
||
Line 132:
==Right 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}
Line 146 ⟶ 147:
:<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.{{cn}}
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 is defined as ''L''<sub>1</sub>/''L''<sub>2</sub> = { ''s'' | ∃''t''∈''L''<sub>2</sub>. ''st''∈''L''<sub>1</sub> }.<ref>Hopcroft, Ullman (1979), Sect.3.2, p.62</ref>
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 {''sa''} / {''b''} yielding {}, rather than { ε }.
==Syntactic relation==
| |||