Quelle est l'expression régulière non générée sur {a, b}?

Question

Je suis vraiment coincé avec ces 2 questions depuis plus de 2 jours maintenant. J'essaie de comprendre ce que la question signifie. Mon tuteur est aussi en dehors de la ville.

Question 1: Écrivez une expression régulière pour les seules chaînes qui ne sont pas générées sur {a, b} par l'expression: (a+b)****a(a+b)****. Explique ton raisonnement.

Et j'ai essayé la deuxième question. Pensez-vous qu'il y a une meilleure réponse que celle-ci?

Qu'est-ce qu'une expression régulière d'un ensemble de chaînes qui contiennent un nombre impair de a s ou exactement deux b s (a((a|b)(a|b))****|bb) Je sais que pour représenter une longueur impaire de A, le RE est a((a|b)(a|b))****

Answer 1

est ici un début pour la première question. Considérons d'abord les cordes que cette expression régulière génère:

(a+b)*a(a+b)* 

• Il doit commencer par a ET
• Chaque b doit avoir au moins un un a immédiatement avant et
• Il doit être soit un aab ou bien la chaîne doit se terminer par a.

L'inverse de ceci est:

• Il ne faut pas commencer par a OU
• Il y a au moins un b pas après une a OU
• La chaîne ne se compose que de répétitions de ab .

Pour la deuxième question, vous devez vérifier que vous avez bien compris la question. Votre interprétation semble être:

Quelle est l'expression régulière pour l'ensemble des chaînes qui contiennent soit (un nombre impair de A et un certain nombre de B) ou (exactement deux b et pas un de).

Mais une autre interprétation est la suivante:

Quelle est l'expression régulière pour l'ensemble des chaînes qui contiennent soit (un nombre impair de A et un nombre quelconque de b) ou (exactement deux b et n'importe quel nombre de).

Answer 2

Pour correspondre à deux a vous utiliseriez quelque chose comme aa? Maintenant nous savons que le + est un quantificateur pour 1 ou plus et le * est un quantificateur pour 0 ou plus. Donc, si nous voulons répéter ce motif entier, nous pouvons le mettre dans un groupe et répéter le motif entier comme suit: (aa)+.

qui correspondrait:

• aa
• aaaa

Mais pas:

• a (parce que aa nécessite au moins 2 articles) `
• aaa (parce que aa correspondra aux deux premières, mais vous aurez un a supplémentaire)

Et si nous voulons faire cela bizarre un même, nous pouvons simplement ajouter un a supplémentaire en dehors du groupe comme si : a(aa)+. Cependant, comme nous voulions un montant impair sans minimum spécifique, nous ne devrions pas utiliser + car cela nécessiterait au moins 3 a.

La réponse entière serait: (bb|a(aa)*)

Answer 3

Il semble que la première question vous demande d'écrire une expression régulière pour l'ensemble des chaînes qui ne correspondent pas à la condition expression régulière.

Par exemple, supposons que la question demandait une expression régulière pour l'ensemble de chaînes et non correspondant à aa+ sur {a}. Eh bien, voici quelques chaînes qui ne correspondent:

• 'aa'
• 'AAAA'
• 'AAAAA'

Quelles sont certaines chaînes qui ne correspondent pas? Voici les deux seuls:

• ''
• 'a'

A regex pour ce dernier ensemble est a?.

En ce qui concerne la deuxième question, je suggérerais de roder quelques cas de test positifs et négatifs. Exécutez quelques chaînes comme celui-ci par votre regex et de voir ce qui se passe:

• 'a' (doit passer)
• 'aaa' (doit passer)
• 'bb' (doit passer)
• ' »(échouait)
• 'aa' (échouait)
• 'aba' (échouait)

Bonne chance!

Answer 4

L'expression (a+b)*a(a+b)* signifie simplement: il a pour être un a à l'intérieur de la chaîne. Les seules chaînes qui ne peuvent pas être générées par cette expression sont les suivantes: b*

Answer 5

Cette expression signifie que RE doit contenir Atleast 1 'A' dans l'expression.

cette expression ne fais pas accepter

'b' 'b' * ou ensemble vide