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.

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

Version videVersion à trous

Évaluations restantes : 10/10

.128013:Lp%(4îed3; 1Eo5_An)h]6,qc[yFCuvà8i2xms7=wlSatf9OR|rg.*éPkbè/050j0i0U0T0J0R0N0m0A0R0T0N0N0P010U0J0d010406050N0F0M0M0T0!0C040S0p0R0F110p0t0m020T0M0d0l0m0Y0i1b0!0z0F0i0N050-181a1c1e160d041C1J051M0-1M1O1J160j0J0G0_0{0}0 0v0J0#0v0R1$0v0U14050;0+0R0i1X0|0~011#1%1)1%0U1/1;1-0U0+0p0j1e1.0!1K0U0v0_1h0N0d0T0t0 0K011?1Z010V0?0i0t1p0i1-2e2g2l1^2o1;2r0M2t040a0m0)0!0p0d0p0N0J1k1m0/2c0!0!0i0A2O1C2v0t1K0-2a2!0U2827290j2x0 1)0t2q2L1-1U1W0`1@2.0J2:0t241V1-0d2T1K2Y2!35172f1m2_2m2~0!1b0R140n2X3915382w3b1^3d3f140K3j2g3l2Y2-013q0T3g040k3u2Z163x3o0 3A3C0g3F3w393y3L140q3O3H3Q3J3z0p3e3B140x3V3m3a1Y3p3!3r040O3)3I3,3K3.3$040I3O1L331C2@2%0j2+3y0A242D0.1V1K320i343k3}460/4e3n3@010*140/0V3}3?2`010Q140m4r3X4l0t0V14462S1A2K0t0j4y4k4t13040f4K3+4t0t4D0v0=2:4Q3y4N0y3O4x4s3c142T0#1;1B1D4f4(1^4!4$3*3R4o0i0+1j4Y3Y4?4/3v4%4z4S142o0t4~4l4N0u0b3V0m5f534L4)040:0T0U4@4;0 0p140P5o545j0/4|5n513G5g5h4R2m4n040V3!5u5i3p4D1c0T2V0i2T5K5E1^0p4v042|5T4_040A4V2|0i594M145d5A155C5C4^3Y5G0J4q5/5D4Z144P5/5?4A145l5z375p0150355|3Y4T5$5O5Q5S60675b5!3Y5W145Z5{6155044+4-5+2m4N5.35065;6C6b625k0;653k6E4t5r045t6q676d6u1A6w4=140B5 665v5M6G5m6U0 696J6r5j0A6f0U5R5*6i6!6)140u0w5e6D6,1^5G0i0@6=6Z5L6^046z3k6B6D5=675G2T0U0F0!586P6@4m0A140D3B0N73797c7l7e0:7h7j6a6~3K636H6l4l6M0P6O7A6Q566p6A1C4h4d3~7R0-411C0U437W2)2#23252%0T1:7T411I4j5U0 2T0M0r0V0T0*0i0r0v0k141u1w1y1A0m783v1L3l1J0X1m0(7g1U1=0J0A0J0m0/0^051v040T1j0p1b6:0^570J0^0j8b5R0M2|8v8s1C8m0m2f0!110A0F1)5R0N0$2G0p7h8G8R0G0p0J0!0m2(0=6:8Y0U8R0^4-0m8o8(8r828u8w8y3e8B0N8s0y0m0?0m1b0t810m0{8T0}0J0+0?2N0(8i000T8V8X8G1i2M0i7h0^8b5m8t2|8o0L0$867-898G9j0U8~1l2(5R0m910A828-8q5m820d8z0:6:0t9y2Q2T320(7r9P9C0R002q7r0M7*8i82050T0m0v2T0V1!1~0d0N0b0-0-0V0!0$0Q0J0*120i1U0T0$3!0#0-9}9 0-0o0L4c951l0r0!0e0E0k0e0s0W0#8L0Jaiak0s0I2T63ac2Tae0t0^0!0(ao1)0,ay1C0T040m0f0:0maC8g320p812C9P0u9s1P87040c820iax1A2M1laBaDapaG820N9A9(0^5%0T0h2:8w1=6.0!5P0Ua/0^9L3e9N2g9Q1=8x0A0!8X1=aN0j1l0A9b0J0/9P5_0J9C0j9c1jay0_4Va`822Qa~b0b28P0)1c0ma%1v0d1;8{9Y9H8/0_998i2g8*000(2~0t0A9a4Eay4H2,0H929Za(azaOa-aF2T4x7Q4O7)0%0A0u0%0T0T0Z0+7P4704aX1S405l0?0N04.

Évaluations restantes : 10/10

.128013:Lp%(4îed3; 1Eo5_An)h]6,qc[yFCuvà8i2xms7=wlSatf9OR|rg.*éPkbè/050j0i0U0T0J0R0N0m0A0R0T0N0N0P010U0J0d010406050N0F0M0M0T0!0C040S0p0R0F110p0t0m020T0M0d0l0m0Y0i1b0!0z0F0i0N050-181a1c1e160d041C1J051M0-1M1O1J160j0J0G0_0{0}0 0v0J0#0v0R1$0v0U14050;0+0R0i1X0|0~011#1%1)1%0U1/1;1-0U0+0p0j1e1.0!1K0U0v0_1h0N0d0T0t0 0K011?1Z010V0?0i0t1p0i1-2e2g2l1^2o1;2r0M2t040a0m0)0!0p0d0p0N0J1k1m0/2c0!0!0i0A2O1C2v0t1K0-2a2!0U2827290j2x0 1)0t2q2L1-1U1W0`1@2.0J2:0t241V1-0d2T1K2Y2!35172f1m2_2m2~0!1b0R140n2X3915382w3b1^3d3f140K3j2g3l2Y2-013q0T3g040k3u2Z163x3o0 3A3C0g3F3w393y3L140q3O3H3Q3J3z0p3e3B140x3V3m3a1Y3p3!3r040O3)3I3,3K3.3$040I3O1L331C2@2%0j2+3y0A242D0.1V1K320i343k3}460/4e3n3@010*140/0V3}3?2`010Q140m4r3X4l0t0V14462S1A2K0t0j4y4k4t13040f4K3+4t0t4D0v0=2:4Q3y4N0y3O4x4s3c142T0#1;1B1D4f4(1^4!4$3*3R4o0i0+1j4Y3Y4?4/3v4%4z4S142o0t4~4l4N0u0b3V0m5f534L4)040:0T0U4@4;0 0p140P5o545j0/4|5n513G5g5h4R2m4n040V3!5u5i3p4D1c0T2V0i2T5K5E1^0p4v042|5T4_040A4V2|0i594M145d5A155C5C4^3Y5G0J4q5/5D4Z144P5/5?4A145l5z375p0150355|3Y4T5$5O5Q5S60675b5!3Y5W145Z5{6155044+4-5+2m4N5.35065;6C6b625k0;653k6E4t5r045t6q676d6u1A6w4=140B5 665v5M6G5m6U0 696J6r5j0A6f0U5R5*6i6!6)140u0w5e6D6,1^5G0i0@6=6Z5L6^046z3k6B6D5=675G2T0U0F0!586P6@4m0A140D3B0N73797c7l7e0:7h7j6a6~3K636H6l4l6M0P6O7A6Q566p6A1C4h4d3~7R0-411C0U437W2)2#23252%0T1:7T411I4j5U0 2T0M0r0V0T0*0i0r0v0k141u1w1y1A0m783v1L3l1J0X1m0(7g1U1=0J0A0J0m0/0^051v040T1j0p1b6:0^570J0^0j8b5R0M2|8v8s1C8m0m2f0!110A0F1)5R0N0$2G0p7h8G8R0G0p0J0!0m2(0=6:8Y0U8R0^4-0m8o8(8r828u8w8y3e8B0N8s0y0m0?0m1b0t810m0{8T0}0J0+0?2N0(8i000T8V8X8G1i2M0i7h0^8b5m8t2|8o0L0$867-898G9j0U8~1l2(5R0m910A828-8q5m820d8z0:6:0t9y2Q2T320(7r9P9C0R002q7r0M7*8i82050T0m0v2T0V1!1~0d0N0b0-0-0V0!0$0Q0J0*120i1U0T0$3!0#0-9}9 0-0o0L4c951l0r0!0e0E0k0e0s0W0#8L0Jaiak0s0I2T63ac2Tae0t0^0!0(ao1)0,ay1C0T040m0f0:0maC8g320p812C9P0u9s1P87040c820iax1A2M1laBaDapaG820N9A9(0^5%0T0h2:8w1=6.0!5P0Ua/0^9L3e9N2g9Q1=8x0A0!8X1=aN0j1l0A9b0J0/9P5_0J9C0j9c1jay0_4Va`822Qa~b0b28P0)1c0ma%1v0d1;8{9Y9H8/0_998i2g8*000(2~0t0A9a4Eay4H2,0H929Za(azaOa-aF2T4x7Q4O7)0%0A0u0%0T0T0Z0+7P4704aX1S405l0?0N04.