Talk:Brzozowski derivative

Latest comment: 6 years ago by Jochen Burghardt in topic Simplification

δ should not be used for "nullable"

edit

In the article δ is used to denote the auxiliary function that checks whether the given language contains the empty word. So this is not the derivative, as the name "δ" suggests. The derivative is the function a^-1.

I suggest to instead use ν (for "nullable") for the auxiliary function that checks whether the empty word is contained in the language. Also, giving first the definition of the main function (derivative) and then the auxiliary function (nullable) might help the quick reader. Andreasabel (talk) 13:53, 1 August 2016 (UTC)Reply

I agree, and have changed the article accordingly. - Jochen Burghardt (talk) 16:15, 1 August 2016 (UTC)Reply
Great, thanks! Andreasabel (talk) 08:28, 2 August 2016 (UTC)Reply

Inconsistent use of “ε”

edit

First the article states that ε denotes “the singleton set containing just the empty string“. Later ε is called “the empty string”. 80.142.135.220 (talk) 20:41, 7 May 2016 (UTC)Reply

You are right; that is a notational sloppiness which is, however, common in regular expressions. A similar issue concerns alphabet symbols: the regular expression a denotes the set {a}. - Jochen Burghardt (talk) 23:15, 7 May 2016 (UTC)Reply

Rules for v(R) are incomplete

edit

There is no rule that applies when R is a single, fixed symbol -- it looks like there should be a case for v(b), just as there is for a-1b. I haven't added it as I don't have access to the original paper source to confirm this.

101.175.24.183 (talk) —Preceding undated comment added 12:25, 14 January 2017 (UTC)Reply

Simplification

edit

It looks to me like ν(R) = (Rε)

Is there any convention for why it is not written that way? Eassin (talk) 19:29, 26 September 2018 (UTC)Reply

Now that you say it - it looks correct to me. I don't know why Brzozowski didn't define it in that way in his 1964 paper. One possible reason could be that your definition essentially relies on generalized regular expressions (admitting "∧"), while Brzozowski's definition can be rephrased such that "∧" isn't needed: define ν(RS)=ε if both ν(R)=ε and ν(S)=ε; define ν(RS)=∅, otherwise. Thus, his definitions of u−1R, of a−1R and -rephrased- of ν(R) would still work for ordinary regular expressions. - Jochen Burghardt (talk) 08:56, 27 September 2018 (UTC)Reply