Langages réguliers qui ne peuvent pas être exprimés avec seulement 2 opérations regex

12

Je pensais que toutes les langues régulières pouvaient être exprimées avec des expressions régulières (si une langue est régulière, elle peut être exprimée avec regex), mais on m'a dit que vous avez besoin des trois opérations régulières (concaténation, union et étoile) pour cela tenir.

Par exemple, on m'a dit que si je n'utiliser les syndicats et concaténation opérations regex (2 sur 3), il y aurait une langue régulière , je ne peux pas décrire avec seulement ces deux.

Même chose avec juste la star et l'union de Kleene. Quels sont quelques exemples de cela?

user3295674
la source

Réponses:

19

Avec seulement l'union et la concaténation, vous ne pouvez décrire aucun langage infini. L'union et la concaténation ne peuvent produire qu'un nombre fini de chaînes. Avec seulement l'union et l'étoile de Kleene, vous ne pouvez pas décrire un langage tel que , car il n'y a aucun moyen de concaténer une expression générant uniquement a avec une expression générant uniquement b . Avec seulement la concaténation et l'étoile de Kleene, vous ne pouvez pas décrire un langage tel que L = { a , b } .L={ab}abL={a,b}

DylanSp
la source
3
{a,b}
Alors pourquoi ne puis-je pas décrire L = {a, b} sans union? Est-ce parce qu'ils ne peuvent pas être représentés comme des éléments séparés avec une étoile et une concaténation? Il ne pouvait que faire ab, bb, aba etc.?
user3295674
@ user3295674 Exactement.
DylanSp
et quelque chose comme L = {a *} ne serait pas possible avec juste l'union et la concaténation, non? Merci beaucoup!
user3295674
Je ne comprends même pas comment l'étoile serait définie sans que la concaténation soit disponible.
G. Bach
11

(abc)dddd1

Yuval Filmus
la source
4

A(ab)(a(ab)b)(aa)

Si l'on permet désormais d'utiliser des étoiles mais pas des étoiles imbriquées , alors c'est un problème ouvert (depuis au moins 45 ans) de savoir si l'on peut obtenir toutes les langues régulières. Cette question est connue sous le nom de problème généralisé de hauteur des étoiles . Il est similaire au problème de hauteur d'étoile mentionné par Yuval Filmus, à la différence près que la complémentation est désormais autorisée.

J.-E. Épingle
la source