Quel est le Set défini par cette expression régulière?

Question

J'essaie de passer à travers des questions d'expression régulière et de langue, mais celui-ci semble m'avoir bloqué.

Quelqu'un peut-il aider?

Je suis en train d'écrire l'ensemble qui est défini par cette expression régulière:

Answer 1

Pour comprendre cette expression régulière, permet de considérer séparément ses trois parties:

(a | Ɛ) abb (a | b)
\ --- 1 ---- --2 --- --- 3 ---
_{cette expression régulière est définie en trois groupes/pièces à l'aide de parenthèses}

Part-1: Ɛ est un symbole nul dans l'expression régulière, si elle apparaît avec un autre symbole (ou un groupe de symboles) avec l'opérateur syndical | cela signifie que le symbole (ou le groupe) est l'option, par ex. peut apparaître ou ne pas apparaître dans certaines chaînes de langage (Ɛ symboles dans FA comme étiquette de bordure définit 'transition nulle' — qui permet une transformation vers un nouvel état sans consommer de symboles d'entrée).

Dans votre expression régulière, le premier 'a' s'écrit avec Ɛ — (a | Ɛ) donc c'est une option - il peut apparaître dans une chaîne ou absent dans une autre chaîne. Par conséquent, les chaînes générées en utilisant cette expression régulière commencent par deux 'a' ou un 'a'.

Partie-2: La sous-chaîne 'aab' apparaît toujours dans toutes les chaînes possibles en utilisant cette expression régulière.

si les chaînes peuvent être sous deux formes possibles:

1. AABB (a | b)
2. abb (a | b)

Partie 3: (a | b) chaîne se termine par le symbole «a» ou le symbole «b».

si les deux formes ci-dessus se termine par 'a'

• aabba
• abba

si les deux formes ci-dessus se termine par 'b'

• aabbb
• abbb

-sûr, il est un langage fini et son DFA ne contient aucune boucle. Son DFA pour cette langue {aabba, abba, aabbb, abbb} serait comme suit: