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

.128013s3_8èufvy |n7aS1me(P24C:twi][hE*)6Oo;bcdg/lîàqAp.rFL,=k%95Rxé050O0s0z0o0B0R0b0k0N0R0o0b0b0$010z0B0W010406050b0g0r0r0o0Y0j040p0K0R0g110K0m0k020o0r0W0L0k0+0s1b0Y0U0g0s0b050Q181a1c1e160W041C1J051M0Q1M1O1J160O0B0i0_0{0}0 0E0B0P0E0R1$0E0z14050;0M0R0s1X0|0~011#1%1)1%0z1/1;1-0z0M0K0O1e1.0Y1K0z0E0_1h0b0W0o0m0 0v011?1Z010h0?0s0m1p0s1-2e2g2l1^2o1;2r0r2t040a0k0u0Y0K0W0K0b0B1k1m0/2c0Y0Y0s0N2O1C2v0m1K0Q2a2!0z2827290O2x0 1)0m2q2L1-1U1W0`1@2.0B2:0m241V1-0W2T1K2Y2!35172f1m2_2m2~0Y1b0R140q2X3915382w3b1^3d3f140v3j2g3l2Y2-013q0o3g040c3u2Z163x3o0 3A3C0w3F3w393y3L140*3O3H3Q3J3z0K3e3B140I3V3m3a1Y3p3!3r040n3)3I3,3K3.3$040e3O1L331C2@2%0O2+3y0N242D0.1V1K320s343k3}460/4e3n3@010%140/0h3}3?2`010A140k4r3X4l0m0h14462S1A2K0m0O4y4k4t13040t4K3+4t0m4D0E0=2:4Q3y4N0#3O4x4s3c142T0P1;1B1D4f4(1^4!4$3*3R4o0s0M1j4Y3Y4?4/3v4%4z4S142o0m4~4l4N0H0y3V0k5f534L4)040:0o0z4@4;0 0K140$5o545j0/4|5n513G5g5h4R2m4n040h3!5u5i3p4D1c0o2V0s2T5K5E1^0K4v042|5T4_040N4V2|0s594M145d5A155C5C4^3Y5G0B4q5/5D4Z144P5/5?4A145l5z375p0150355|3Y4T5$5O5Q5S60675b5!3Y5W145Z5{6155044+4-5+2m4N5.35065;6C6b625k0;653k6E4t5r045t6q676d6u1A6w4=140D5 665v5M6G5m6U0 696J6r5j0N6f0z5R5*6i6!6)140H0C5e6D6,1^5G0s0@6=6Z5L6^046z3k6B6D5=675G2T0z0g0Y586P6@4m0N140Z3B0b73797c7l7e0:7h7j6a6~3K636H6l4l6M0$6O7A6Q566p6A1C4h4d3~7R0Q411C0z437W2)2#23252%0o1:7T411I4j5U0 2T0r0d0h0o0%0s0d0E0c141u1w1y1A0k783v1L3l1J0J1m0-7g1U1=0B0N0B0k0/0^051v040o1j0K1b6:0^570B0^0O8b5R0r2|8v8s1C8m0k2f0Y110N0g1)5R0b0X2G0K7h8G8R0i0K0B0Y0k2(0=6:8Y0z8R0^4-0k8o8(8r828u8w8y3e8B0b8s0#0k0?0k1b0m810k0{8T0}0B0M0?2N0-8i000o8V8X8G1i2M0s7h0^8b5m8t2|8o0,0X867-898G9j0z8~1l2(5R0k910N828-8q5m820W8z0:6:0m9y2Q2T320-7r9P9C0R002q7r0r7*8i82050o0k0E2T0h1!1~0W0b0y0Q0Q0h0Y0X0A0B0%120s1U0o0X3!0P0Q9}9 0Q0F0,4c951l0d0Y0(0x0c0(0V0)0P8L0Baiak0V0e2T63ac2Tae0m0^0Y0-ao1)0fay1C0o040k0t0:0kaC8g320K812C9P0H9s1P87040!820sax1A2M1laBaDapaG820b9A9(0^5%0o0S2:8w1=6.0Y5P0za/0^9L3e9N2g9Q1=8x0N0Y8X1=aN0O1l0N9b0B0/9P5_0B9C0O9c1jay0_4Va`822Qa~b0b28P0u1c0ka%1v0W1;8{9Y9H8/0_998i2g8*000-2~0m0N9a4Eay4H2,0T929Za(azaOa-aF2T4x7Q4O7)0G0N0H0G0o0o0l0M7P4704aX1S405l0?0b04.

Évaluations restantes : 10/10

.128013s3_8èufvy |n7aS1me(P24C:twi][hE*)6Oo;bcdg/lîàqAp.rFL,=k%95Rxé050O0s0z0o0B0R0b0k0N0R0o0b0b0$010z0B0W010406050b0g0r0r0o0Y0j040p0K0R0g110K0m0k020o0r0W0L0k0+0s1b0Y0U0g0s0b050Q181a1c1e160W041C1J051M0Q1M1O1J160O0B0i0_0{0}0 0E0B0P0E0R1$0E0z14050;0M0R0s1X0|0~011#1%1)1%0z1/1;1-0z0M0K0O1e1.0Y1K0z0E0_1h0b0W0o0m0 0v011?1Z010h0?0s0m1p0s1-2e2g2l1^2o1;2r0r2t040a0k0u0Y0K0W0K0b0B1k1m0/2c0Y0Y0s0N2O1C2v0m1K0Q2a2!0z2827290O2x0 1)0m2q2L1-1U1W0`1@2.0B2:0m241V1-0W2T1K2Y2!35172f1m2_2m2~0Y1b0R140q2X3915382w3b1^3d3f140v3j2g3l2Y2-013q0o3g040c3u2Z163x3o0 3A3C0w3F3w393y3L140*3O3H3Q3J3z0K3e3B140I3V3m3a1Y3p3!3r040n3)3I3,3K3.3$040e3O1L331C2@2%0O2+3y0N242D0.1V1K320s343k3}460/4e3n3@010%140/0h3}3?2`010A140k4r3X4l0m0h14462S1A2K0m0O4y4k4t13040t4K3+4t0m4D0E0=2:4Q3y4N0#3O4x4s3c142T0P1;1B1D4f4(1^4!4$3*3R4o0s0M1j4Y3Y4?4/3v4%4z4S142o0m4~4l4N0H0y3V0k5f534L4)040:0o0z4@4;0 0K140$5o545j0/4|5n513G5g5h4R2m4n040h3!5u5i3p4D1c0o2V0s2T5K5E1^0K4v042|5T4_040N4V2|0s594M145d5A155C5C4^3Y5G0B4q5/5D4Z144P5/5?4A145l5z375p0150355|3Y4T5$5O5Q5S60675b5!3Y5W145Z5{6155044+4-5+2m4N5.35065;6C6b625k0;653k6E4t5r045t6q676d6u1A6w4=140D5 665v5M6G5m6U0 696J6r5j0N6f0z5R5*6i6!6)140H0C5e6D6,1^5G0s0@6=6Z5L6^046z3k6B6D5=675G2T0z0g0Y586P6@4m0N140Z3B0b73797c7l7e0:7h7j6a6~3K636H6l4l6M0$6O7A6Q566p6A1C4h4d3~7R0Q411C0z437W2)2#23252%0o1:7T411I4j5U0 2T0r0d0h0o0%0s0d0E0c141u1w1y1A0k783v1L3l1J0J1m0-7g1U1=0B0N0B0k0/0^051v040o1j0K1b6:0^570B0^0O8b5R0r2|8v8s1C8m0k2f0Y110N0g1)5R0b0X2G0K7h8G8R0i0K0B0Y0k2(0=6:8Y0z8R0^4-0k8o8(8r828u8w8y3e8B0b8s0#0k0?0k1b0m810k0{8T0}0B0M0?2N0-8i000o8V8X8G1i2M0s7h0^8b5m8t2|8o0,0X867-898G9j0z8~1l2(5R0k910N828-8q5m820W8z0:6:0m9y2Q2T320-7r9P9C0R002q7r0r7*8i82050o0k0E2T0h1!1~0W0b0y0Q0Q0h0Y0X0A0B0%120s1U0o0X3!0P0Q9}9 0Q0F0,4c951l0d0Y0(0x0c0(0V0)0P8L0Baiak0V0e2T63ac2Tae0m0^0Y0-ao1)0fay1C0o040k0t0:0kaC8g320K812C9P0H9s1P87040!820sax1A2M1laBaDapaG820b9A9(0^5%0o0S2:8w1=6.0Y5P0za/0^9L3e9N2g9Q1=8x0N0Y8X1=aN0O1l0N9b0B0/9P5_0B9C0O9c1jay0_4Va`822Qa~b0b28P0u1c0ka%1v0W1;8{9Y9H8/0_998i2g8*000-2~0m0N9a4Eay4H2,0T929Za(azaOa-aF2T4x7Q4O7)0G0N0H0G0o0o0l0M7P4704aX1S405l0?0b04.