Content deleted Content added
→Right quotient: add and source H+U's (more general) def.; mention deviation to unsourced old version (suspected to be flawed/unusual) |
→Right quotient: relate to Brzozowski derivative |
||
Line 151:
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 { ε }.
The left quotient (when definied 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=JACM| year=1964| volume=11| pages=481–494| doi=10.1145/321239.321249}}</ref>
==Syntactic relation==
| |||