La nullabilité (expressions régulières)

Question

« Les dérivés d'expressions régulières » et ailleurs, la fonction de ô Dans Brzozowski (R) de retour ? si un R peut être nulle, et Ø autrement, comprend des clauses telles que les suivantes:

δ(R1 + R2) = δ(R1) + δ(R2)
δ(R1 · R2) = δ(R1) ∧ δ(R2)

Il est clair que, si les deux R1 et R2 sont nullable puis ( R1 · R2 ) est annulable, et si soit R1 ou R2 est annulable puis ( R1 + R2 ) est annulable. On ne sait pas pour moi ce que les clauses ci-dessus sont censés signifier, cependant. Ma première pensée, la cartographie (+), (·) ou les opérations booléennes à des ensembles réguliers est absurde, puisque dans le cas de base,

δ(a) = ∅ (for all a ∈ Σ)
δ(λ) = λ
δ(∅) = ∅

et ? est pas un ensemble (ni est un ensemble du type de retour de d, qui est une expression régulière). De plus, cette application n'est pas indiqué, et il y a une notation distincte pour elle. Je comprends la nullabilité, mais je suis perdu sur la définition de la somme, le produit et les opérations booléennes dans la définition de d: comment sont ? ou Ø retour de d ( R1 ) ? d ( R2 ), par exemple, dans la définition de d ( R1 R2 · )?

Answer 1

Je pense que vous allez vous surprendre par les libertés prises par l'notationnelles auteur. Le type de retour de d (R) est certainement un ensemble, ou plutôt une langue. Si vous regardez la définition:

vous pouvez voir qu'il ya une incohérence dans le type de retour, formellement ? est un élément, mais Ø est la langue vide ... Ce qu'il faut dire est:

Le fait que l'auteur utilise X tant pour la chaîne vide, ainsi que la langue ne contenant que la chaîne vide est également attestée par sa définition de l'opérateur étoiles Kleene:

Il est clair que la dernière partie doit être si nous voulons être pédant.

Étant donné que le type de retour de d (R) est un ensemble, ou plutôt une langue, les équations que vous donnez un sens parfait et exprimer exactement ce que vous avez décrit.

Answer 2

Je pense que vous aviez raison de la carte + et ^ à or booléens et and respectivement. Il semble que les deux lignes que vous avez cités accord avec alternance (somme) et concaténation (produit):

δ(R1 + R2) = δ(R1) + δ(R2)

alternance de R1 et R2 est annulable si R1 est annulable, R2is annulable, ou les deux R1 et R2 sont annulable.

δ(R1 · R2) = δ(R1) ∧ δ(R2)

concaténation de R1 et R2 est seulement annulable si les deux R1 et R2 sont annulable.

Voir pour une mise en œuvre de ces règles Haskell.

Answer 3

(je ne peux pas regarder dans l'article de Brzozowski afin de mieux comprendre ce qu'on entend là), mais je peux suggérer 2 façons d'interpréter cette notation (en dehors de gettingalong avec la notation, je vois, il n'y a pas question : le sens voulu de cette définition est bien comprise):

1) Sur la gauche de la définition, nous avons seulement des modèles « syntaxique » pour les expressions régulières. A droite, nous produisons des ensembles; rappelez-vous, qu'une expression régulière est un moyen pour désigner une langue (un ensemble), et ainsi de cette façon d'écrire la définition devient compréhensible: à droite, nous utilisons simplement une (simple) des expressions régulières comme une courte façon de se référer à ensembles. À savoir, Ø signifie que la langue vide (ensemble vide) et ? (si interprété comme une expression régulière) signifie que la langue ne contenant que le mot vide (le jeu avec cet élément).

Les opérations sont tout simplement des opérations sur des ensembles: probablement union, intersection et

.

Si la notation est interprétée de cette façon, il n'y a pas de contradiction avec la notation utilisée pour defian le cas de base: à nouveau, « a » est une expression régulière qui est là pour signifier la langue avec le mot « a »

2) Nous construisons expressons régulièrement à droite, en premier lieu, mais l'auteur a étendu les opérations qui construisent des expressions régulières avec le coin, qui a la sémantique d'intersection des langues.