Exercice 7 - Automate et reconnaissance de motif ⭐⭐

On considère les automates décrits dans l'exercice Automate en dictionnaire.

Conseil

On conseille fortement de lire l'exercice cité plus haut afin de se familiariser avec la représentation des automates sous forme de dictionnaires Python.

Un tel automate permet de déterminer si une chaîne de caractère correspond à un certain motif :

  • on débute dans l'état de départ en lisant le premier caractère de la chaîne ;

  • s'il existe une règle correspondant à ce couple « état - caractère lu », on passe dans l'état indiqué par la règle et on lit le caractère suivant ;

  • si une telle règle n'existe pas, la chaîne étudiée ne correspond pas au motif cherché ;
  • une fois tous les caractères de la chaîne lus, si l'on se trouve dans l'état final alors celle-ci correspond au motif.

Par exemple les chaînes "b", "abcaa" et "abbcb" correspondent au motif décrit dans l'automate ci-dessous. Les chaînes "abbc", "abbbd" et "ba" n'y correspondent pas.

Automate

Les automates et leurs règles de transitions sont décrits à l'aide de dictionnaires Python (voir exercice Automate en dictionnaire).

On demande d'écrire la fonction correspond qui :

  • prend en arguments :
    • une chaîne de caractères chaine,
    • une ensemble de règles données sous forme d'un dictionnaire regles,
    • l'état de départ debut,
    • l'état final fin,
  • et renvoie le booléen indiquant si la chaîne proposée satisfait aux règles données.
Exemples
>>> regles = {(0, "a"): 1, (0, "b"): 2, (1, "a"): 2, (1, "b"): 1, (1, "c"): 0}
>>> debut = 0
>>> fin = 2
>>> correspond("b", regles, debut, fin)
True
>>> correspond("abbcaa", regles, debut, fin)
True
>>> correspond("abbcb", regles, debut, fin)
True
>>> correspond("abbc", regles, debut, fin)
False
>>> correspond("abbbd", regles, debut, fin)
False
>>> correspond("ba", regles, debut, fin)
False

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013="_ey3qCdRuéàxEgPvr8-è*fLbcîo/m]h(apl,7)['n sS:|6w% 1ki.F9Ot25;4A030d080$0D0X0F0N0M0v0F0D0N0N05060$0X0E06020U030N0f0z0z0D0n09020O0x0F0f0~0x0L0M000D0z0E0(0M0e08180n0b0f080N030y1517191b130E02031G1z1J0y1G130d0X0m0?0^0`0|0^0L0k0f0D0k080p0E090$0B1i0M0B0X0k0B0F1.0B0$11030.0u0F081S0_0{061-1/1;1/0$1`1|1^0$0n1H1)0?1e0N0E0D0L0|0%061~1U060s0:080L1m081^2g2i2n202q1|2t0z2v02040M0l0n0x0E0x0N0X1h1j0,2e0n0n080v2Q1z2x0L1H0y1)2$2a2c2b1_0d2z1V0X0L2s2N1^1P1R0@1 2/2;0L0x2^1^0E2V1H2!2$35142h1j2`2o2~0n180F1^0D1,2V0s0|0107070v2 081;2}0x0p0V3w110V1z0D363912382y3b203d3f3h3j083l063n3p3r3t2=3w0p2l020%3B3D2i3F2!2.063K0D3g1H3i0B3k3m3o3q0,3U2~3W0a110a3#2Z3E133(3I0|3+3-033/3;3Q3?3T2:3V3x0)110)3 1A413G3a1T3J0x3e3,3M3:3O3=3S3^4e3`3x0'110'4k3542393)464u4a3R3@3s4A3v3x0R110R4G4m434p454r3L3.3N3P4O4d3u3W0H110H4X3%4I3H4!3*4$4t4'4v4)4c4z4,3x0o110o4;2#1K331z2^2(0d2c2-44064P2@1Q1H3208343E403%034P5o2y0X0d0|3o2!3W0V3M5w5y4y4Q513y0M2D085F4P3_4S3y2$3C4n3)0W110,0s5q2#0M5U5g0L0s113q2U1x2M0L0d5!5u4o2{0610020C5;5%4^0L5*0B0/2;5|4Z5@5_0G5;5$653c112V0k1|1y4l5r6b2067695}5@5 020,0u1g644J5g6m6i5#6o6c022q0L6v4@66110I0P5;136z5=0M5E065z393W3Y486Q5x6S5G5P6V2m5L5N4+4f3X1^0y3C0M6:6a6w5~110-0D0$6n6k0|0x11056|6?6p5X086t6{6O6N373(6R6T2i3{5D6Z4 5H6+3|5K2u6)507l6-6/6;6B205W6D4r726H6C0v190D2X082V7A5?2o0x0S112:7J4K6062086G7K6l116L797V6Y5F5A4g7h7p7k4B0p4h7n2E7*6$7(5S026;7_6=7B7w7O5Z6O7{7W0|5_5{6O7v456^0.787b732o6y35817R027D0n7F0$7H7U866}5^6J7Q5g7M7O6F80873*6d086f1x7#6x7Y6M7#7d077'0p4D4'8L5O4R3W4D7/5M6!8S5I8P3#7`8%8h5'896`8u4^6 02718z8r6q6e6g8G4^5_0J858c7|88026_8b5p8r8f3E8(6@8j7E7G7I8q8d7X020I0A8J9e5v7i8M6U4T7)8Y6*7,4U8W7;8T9q7@8'985@7x3s0N8p8~828s027Z4H8K9n8N4.8Q9n8Z6+4.9w9s7q7,9R8$9B7u8r7x2V0$0f0n8y8g8A0W0v110Z3,9G9k9I7$6!8N539S9x5I539X7j7=0p9 9$6:9:8C9+9-8,74918aaf7L708:9/8=116E9`5p0y5t585n5a5k1z0$5daz2+2%0D1{aw0y5b1F6P5g2V0z070s0D0W08070B3|021r1t1v1x0M9Mas1N1I020#1j0g9+1P1}0X0v0X0M0,0=031s020D1g0x188n0=6E0X0=0da-7H0z2:b4b11za{0M2h0n0~0v0f1;7H0N0Y2I0x9,bfbq0m0x0X0n0M2a0/8nbx0$bq0=6g0Ma}bDb0a#b3b5b73eba0Nb10G6Q0F0M180La!0M0^bs0`0X0u0:2P0ga@0K0Dbubwbf1f2O089,0=a-6`b22:a}0i0Y1K3F1Ga+bfb@0$bW1i2a7H0MbZ0va#bIa 6`a#0Eb80-8n0Lc72S2V320g9Gcocb0F0K2s9G0zaGa@a#6X4}0|1?0$0E0N0P0y0y0s0n0Y0S0X0W0 081P0D0Y4r0k0ycScU0y0j0i5mb%1i070n0T0c0a0T0*0!1Y1;c:c=0*0o2V6^c*2Vc,0L0=0n0gc_0X0qd28$0C0-0Md6a=320xa!2Eco0Ic01Mc2020ta#08d11x2O1id5d7bkd9d20M0Nc9cD0=0v610w2;b51}8k8mdacjcl262icp1}b60v0nbw1}de0d1i0vb,5w2s0~2qcb0db-1gdDdJ0DdLa#2SdP2XdRbn2I190Mdu1s0E1|bTcxcgbK0?b*a@2ibF0K0g2~0L0vb+5+d25.2-0hb!cydvd3dfdA1;dR5$5t0CaF0r0v0I0r0D0D0Q0u1z5tdoa(aI6_0:0N02.

###(Dés-)Active le code après la ligne # Tests (insensible à la casse)
(Ctrl+I)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
Évaluations restantes : 5/5

.128013="_ey3qCdRuéàxEgPvr8-è*fLbcîo/m]h(apl,7)['n sS:|6w% 1ki.F9Ot25;4A030d080$0D0X0F0N0M0v0F0D0N0N05060$0X0E06020U030N0f0z0z0D0n09020O0x0F0f0~0x0L0M000D0z0E0(0M0e08180n0b0f080N030y1517191b130E02031G1z1J0y1G130d0X0m0?0^0`0|0^0L0k0f0D0k080p0E090$0B1i0M0B0X0k0B0F1.0B0$11030.0u0F081S0_0{061-1/1;1/0$1`1|1^0$0n1H1)0?1e0N0E0D0L0|0%061~1U060s0:080L1m081^2g2i2n202q1|2t0z2v02040M0l0n0x0E0x0N0X1h1j0,2e0n0n080v2Q1z2x0L1H0y1)2$2a2c2b1_0d2z1V0X0L2s2N1^1P1R0@1 2/2;0L0x2^1^0E2V1H2!2$35142h1j2`2o2~0n180F1^0D1,2V0s0|0107070v2 081;2}0x0p0%0p0V110V1z0D363912382y3b203d3f3h3j083l063n3p3r3t2=3w3w110%3C3E2i3G2!2.063L0D3g1H3i0B3k3m3o3q0,3V2~3X0a110a3#2Z3F133(3J0|3+3-033/3;3R3?3U2:3W3x0)110)3 1A413H3a1T3K0x3e3,3N3:3P3=3T3^4e3`3x0'110'4k3542393)464u4a3S3@3s4A3v3x0R110R4G4m434p454r3M3.3O3Q4O4d3u3X0H110H4X3%4I3I4!3*4$4t4'4v4)4c4z4,3x0o110o4;2#1K331z2^2(0d2c2-44064P2@1Q1H3208343F403%034P5o2y0X0d0|3o2!3X3z4'5w5y4y4Q513y2m2D085F4P3_4S5J2$3D4n3)0W110,0s5q2#0M5U5g0L0s113q2U1x2M0L0d5!5u4o2{0610020C5;5%4^0L5*0B0/2;5|4Z5@5_0G5;5$653c112V0k1|1y4l5r6b2067695}5@5 020,0u1g644J5g6m6i5#6o6c022q0L6v4@66110I0P5;136z5=0M5E065z393X2l5D5x6S5G5P6V5K2u5N4+4f3Y5S020M6.6a6w5~110-0D0$6n6k0|0x11056`6;6p5X086t6_6O6N373(6R6T2i3{3N7b6!4R7e0M5L6(506*3|6,6/6:6H2o5W6D4r707t3K5*190D2X082V7y5?2o0x0S112:7H4K6062086G7I6l116L777T6Q6Y7c0L3X4h6X7m5H6*4h7k6'6Z5O7i4g1^0y3D7r7r6B207v0X5Z6O7s7U0|5_5{6O7|456?0.7679712o6y35827P020v7C7E7G876{5^6J7O5g7K7M6F81883*6d086f1x7Z6x7W6M7Z7g5A4C7f7#7h5I4D7.2E7*6#8M7q7`8Y8z6q6@8c3F8i8u6~8t6=026e6g8F4^5_0J868d7z89028$8:6I02688y8q6q8l0n7D0$7F7S8p8e7V020I0A8I9a5v8O8L0p4U7)7:6)4B9l6%8T9o7n9q9m3#8Y6.8z7v3s0N998^838r027X4H8J9j6U3x4.9n4 7+9q4.8S5M9u9T5Q9Q9y9z7{8q7v2V0$0f0n8x8h9B0v110Z3,9E9g9G7!5F9k539R8P6*539W8U7=0p9~9$9A9(8B9+9-8+728{8bae7J6~6 919b8`6E9_5p0y5t585n5a5k1z0$5day2+2%0D1{av0y5b1F6P5g2V0z070s0D0W08070B7p1r1t1v1x0M9Kar1N1I020#1j0g9+1P1}0X0v0X0M0,0=031s020D1g0x18970=6E0X0=0da+7F0z2:b2a 1za_0M2h0n0~0v0f1;7F0N0Y2I0x9,bdbo0m0x0X0n0M2a0/97bv0$bo0=6g0Ma{bBa~aZb1b3b53eb80Na 0G6Q0F0M180LaY0M0^bq0`0X0u0:2P0ga=0K0Dbsbubd1f2O089,0=a+6^b02:a{0i0Y1K3G1Ga)bdb=0$bU1i2a7F0MbX0vaZbGa}6^aZ0Eb60-970Lc52S2V320g9Ecmc90F0K2s9E0zaFa=aZ484(0|1?0$0E0N0P0y0y0s0n0Y0S0X0W0 081P0D0Y4r0k0ycQcS0y0j0i5mb#1i070n0T0c0a0T0*0!1Y1;c.c:0*0o2V6?c(2Vc*0L0=0n0gc@0X0qd09y0C0-0Md4a:320xaY2Ecm0Ib~1Mc0020taZ08c 1x2O1id3d5bid7d00M0Nc7cB0=0v610w2;b31}9496d8chcj262icn1}b40v0nbu1}dc0d1i0vb*5w2s0~2qc90db+1gdBdH0DdJaZ2SdN2XdPbl2I190Mds1s0E1|bRcvcebI0?b(a=2ibD0K0g2~0L0vb)5+d05.2-0hbYcwdtd1dddy1;dP5$5t0CaE0r0v0I0r0D0D0Q0u1z5tdma%aH6@0:0N02.