DFA minimal pour les mots entiers dans regex

Question

En créant un DFA pour une expression rationnelle, j'ai remarqué que les mots entiers ajoutent au nombre d'états, même si analytiquement, ils ressemblent à regex avec moins d'états.

Par exemple, pour moi, (a | b) + regarde la même chose que (bonjour | monde) +

Si j'avais une chaîne de correspondance, il serait assez facile de trouver/remplacer « bonjour » avec "a" et "monde" avec "b" et viceversa. Donc, ma question est la suivante: pourquoi «bonjour» et «monde» ne sont-ils pas considérés comme des États uniques?

Answer 1

Parce que les DFA sont simples à implémenter avec la définition plus simple des états, au prix d'avoir plus d'états. Ce que vous suggérez est bien pour décrire comment vous voulez qu'un DFA fonctionne, et avoir une correspondance directe avec les DFA traditionnels. Mais cela ne vous permet pas de dire autre chose. Il est similaire à l'utilisation des NFA: ils sont plus faciles à concevoir et (peut-être) à penser, mais n'ont pas plus de puissance, et il existe un algorithme bien défini pour les traduire en DFA (encore une fois, à la coût de l'introduction des états). Pensez aux DFA utilisant des transitions à un seul caractère comme le "langage machine" des expressions régulières (qui ne sont PAS la même chose que regex, pour être pédant).