POSIX BRE peut-il exprimer toutes les langues régulières?

13

Il semble que les «expressions régulières de base» telles que définies par POSIX.1-2008 ne prennent pas en charge l'alternance a|b(bien que certaines implémentations grep reconnaissent la version échappée \|).

Les langues régulières étant fermées par union par définition, cela signifie-t-il que POSIX BRE a moins de pouvoir expressif qu'un automate fini? Ou existe-t-il un moyen de simuler l'alternance en utilisant d'autres constructions?

Steve Kobes
la source

Réponses:

17

En effet le langage POSIX BRE ne peut pas exprimer toutes les expressions régulières car il manque d'alternance. Il ne peut même pas reconnaître toutes les langues finies, sans parler de toutes les langues régulières.

Par exemple, n'est pas reconnaissable en tant que BRE. Pour le prouver, réfléchissez à ce que pourrait être la forme syntaxique de haut niveau:{ab,ba}

  • Il ne peut pas s'agir de l'une des formes à caractère unique car la langue a des mots de longueur .>1
  • Ça ne peut pas être R car cela correspondrait à la chaîne vide.
  • Ce ne peut pas être sauf avec m = n = 1R{m,n}m=n=1 (auquel cas nous revenons au problème d'origine) car cela correspondrait à des chaînes de longueurs différentes ou à la chaîne vide.
  • Il faut donc concaténer: . Considérez maintenant comment un bR1R2ab est reconnu:
    • Si reconnaît a b, alors R 2 ne doit rien reconnaître d'autre que la chaîne vide. Donc R 1 doit reconnaître { a b , b a }R1abR2R1{uneb,bune} et nous revenons au problème d'origine.
    • Si reconnaît a mais pas a b, alors R 2 doit reconnaître b . Mais alors RR1uneunebR2b reconnaît tous les mots de la forme u b R 1 reconnaît u , donc R 1 ne doit pas reconnaître autre chose que a . Il n'y a aucun moyen de reconnaître b a .R1R2ubR1uR1unebune
    • Si ne reconnaît ni a b ni a, alors la seule façon pour R de reconnaître a b est si R 1 reconnaît la chaîne vide, auquel cas nous revenons au problème d'origine comme ci-dessus, mais pour R 2 cette fois.R1unebuneRunebR1R2

Lorsque «nous revenons au problème d'origine», cela signifie que la seule solution pour trouver un BRE reconnaît la langue est de trouver un BRE plus petit qui a la même propriété. Il s'agit d'une descente infinie , il n'y a donc pas de BRE qui ait la propriété souhaitée.

Je ne pense pas qu'il y ait une "belle" caractérisation des langages reconnaissables par BRE, par exemple en tant que langages reconnaissables par une "belle" classe d'automates.

{www{une,b}}\(.*\)\1

Gilles 'SO- arrête d'être méchant'
la source
1
Si vous utilisez un outil comme grep qui peut accepter plusieurs expressions séparées par une nouvelle ligne pour correspondre, prend le produit cartésien de toutes les alternatives possibles (par exemple {ab, ba} {ab, ba} devenant {abba, abba, baab, baba}) suffisant pour être équivalent à une "alternance BRE-plus" donnée et donc à une langue régulière?
Random832
1
@ Random832: Essayez de faire (abc|bac)*.
rici