形式言語勉強会（第2回） - 有限オートマトン

形式言語勉強会 #2 @春日エリアの資料です．

Transcript

1. ༗ݶΦʔτϚτϯͱਖ਼نදݱ ܗࣜݴޠษڧձ #2 @ य़೔ΤϦΞ himkt <himkt@klis.tsukuba.ac.jp>
2. ୈ1ষ: ΦʔτϚτϯͱ͸ ୈ2ষ: ༗ݶΦʔτϚτϯ ୈ3ষ: ༗ݶΦʔτϚτϯͷݶք ୈ4ষ: ਖ਼نදݱ
3. ୈ1ষ: ΦʔτϚτϯͱ͸ ୈ2ষ: ༗ݶΦʔτϚτϯ ୈ3ষ: ༗ݶΦʔτϚτϯͷݶք ୈ4ষ: ਖ਼نදݱ
4. ΦʔτϚτϯͱ͸…ͷલʹܭࢉͱ͸ʁ • ਺஋ܭࢉ͚͕ͩܭࢉͰ͸ͳ͍ • “1 + 1” -> “2” • “aiueo” -> “͍͋͏͓͑” • ίϯϐϡʔλʹ͓͍ͯܭࢉΛ࢘Δͷ͸CPUͱϝϞϦ • ߏ଄͸ඇৗʹෳࡶ • ΦʔτϚτϯɿʮܭࢉʯΛ࣮ߦ͢Δ਺ֶతϞσϧ • ݪ࢝త͔ͭந৅త ͜Ε΋ܭࢉ ͜Ε͸ܭࢉ
5. ΦʔτϚτϯͱ͸ʁ • ೖྗɼग़ྗɼঢ়ଶΛ͍࣋ͬͯΔʢू߹ʣ • ೖྗʹରͯ͠ɼͦͷঢ়ଶʹԠͨ͡ग़ྗΛ͢Δ • ঢ়ଶͷʮભҠʯ͸ঢ়ଶͱه߸ΛҾ਺ͱͯ͠ঢ়ଶΛग़ྗ͢Δؔ਺
 ʹΑͬͯఆٛ͞ΕΔ ྫ: ೖྗ ग़ྗ ঢ়ଶ q0 q1 q2 1 0 ঢ়ଶɿ·Δ͍΍ͭɼભҠɿখ͍͞໼ҹ ʢେ͖͍໼ҹ͸ॳظঢ়ଶʣ f(q0 , 1) = q1 , f(q1 , 0) = q2
6. ΦʔτϚτϯͷछྨ • ܾఆੑ༗ݶΦʔτϚτϯ • ඇܾఆੑ༗ݶΦʔτϚτϯ • ܾఆੑϓογϡμ΢ϯΦʔτϚτϯ • ඇܾఆੑϓογϡμ΢ϯΦʔτϚτϯ • ܾఆੑνϡʔϦϯάϚγϯ • ඇܾఆੑνϡʔϦϯάϚγϯ ෳࡶ ؆ૉ
7. ୈ1ষ: ΦʔτϚτϯͱ͸ ୈ2ষ: ༗ݶΦʔτϚτϯ ୈ3ষ: ༗ݶΦʔτϚτϯͷݶք ୈ4ষ: ਖ਼نදݱ
8. ༗ݶΦʔτϚτϯ…ͦͷલʹɼݴޠͱ͸ʁ • ͋ΔΦʔτϚτϯ͕डཧ͢Δه߸ྻͷू߹Λݴޠͱ͍͏ • ΦʔτϚτϯ͸ݴޠΛʮೝࣝʯ͢Δ • ྫ: ݴޠɹɹɹɹɹɹɹɹɹɹɹɹɹ Λೝࣝ͢ΔΦʔτϚτϯ • “f”, “fl”, “ffl”, “fll”, … • ͜ͷه߸ྻͷू߹͕ݴޠʢ͜ͷ৔߹͸ແݶू߹ʣ L = {filj|i 1, j 0}
9. ܾఆੑ༗ݶΦʔτϚτϯͱ͸ʁ • 3ͭͷू߹ɼ1ͭͷؔ਺ɼ1ͭͷཁૉʹΑͬͯߏ੒͞ΕΔ • ঢ়ଶू߹ɼೖྗه߸ू߹ɼडཧঢ়ଶɼঢ়ଶભҠؔ਺ɼॳظঢ়ଶ • ܗࣜతʹ͸ɿ • ྫɿݴޠɹɹɹɹɹɹɹɹɹɹɹɹɹ Λೝࣝ͢ΔΦʔτϚτϯ M = (Q, , , q0 , F) L = {filj|i 1, j 0} Q = {q0 , q1 , q2 } = {f, l} (q0, f) = q1, (q1, f) = q1, (q0, l) = q2, (q2, l) = q2 q0 F = {q1, q2 }
10. ܾఆੑ༗ݶΦʔτϚτϯͱ͸ʁ • 3ͭͷू߹ɼ1ͭͷؔ਺ɼ1ͭͷཁૉʹΑͬͯߏ੒͞ΕΔ • ঢ়ଶू߹ɼೖྗه߸ू߹ɼडཧঢ়ଶɼঢ়ଶભҠؔ਺ɼॳظঢ়ଶ • ܗࣜతʹ͸ɿ • ྫɿݴޠɹɹɹɹɹɹɹɹɹɹɹɹɹ Λೝࣝ͢ΔΦʔτϚτϯ q0 q1 q2 f l l f M = (Q, , , q0 , F) L = {filj|i 1, j 0}
11. ʮඇʯܾఆੑ༗ݶΦʔτϚτϯͱ͸ʁ • 3ͭͷू߹ɼ1ͭͷؔ਺ɼ1ͭͷཁૉʹΑͬͯߏ੒͞ΕΔ • ঢ়ଶू߹ɼೖྗه߸ू߹ɼडཧঢ়ଶɼঢ়ଶભҠؔ਺ɼॳظঢ়ଶ • ܗࣜతʹ͸ɿ • ྫɿݴޠɹɹɹɹɹɹɹɹɹɹɹɹɹ Λೝࣝ͢ΔΦʔτϚτϯ M = (Q, , , q0 , F) L = {filj|i 1, j 0} Q = {q0 , q1 } = {f, l} (q0, f) = {q0, q1 }, (q1, l) = q1 q0 F = {q1 }
12. ʮඇʯܾఆੑ༗ݶΦʔτϚτϯͱ͸ʁ • 3ͭͷू߹ɼ1ͭͷؔ਺ɼ1ͭͷཁૉʹΑͬͯߏ੒͞ΕΔ • ঢ়ଶू߹ɼೖྗه߸ू߹ɼडཧঢ়ଶɼঢ়ଶભҠؔ਺ɼॳظঢ়ଶ • ܗࣜతʹ͸ɿ • ྫɿݴޠɹɹɹɹɹɹɹɹɹɹɹɹɹ Λೝࣝ͢ΔΦʔτϚτϯ M = (Q, , , q0 , F) L = {filj|i 1, j 0} q0 f f l q1
13. ܾఆੑ༗ݶΦʔτϚτϯʁඇܾఆੑ༗ݶΦʔτϚτϯʁ q0 q1 q2 q0 f l f f l l f 1. ܾఆੑ༗ݶΦʔτϚτϯ 2. ඇܾఆੑ༗ݶΦʔτϚτϯ • ༗ݶΦʔτϚτϯͷঢ়ଶભҠؔ਺͸ೖྗʹରͯ͠ग़ྗ͕Ұҙʹܾ·Δ • ඇܾఆΦʔτϚτϯͷঢ়ଶભҠؔ਺͸ೖྗʹରͯ͠ෳ਺ͷग़ྗ͕͋Γ͏Δ • ભҠͷ࢓ํ͕ෳ਺ߟ͑ΒΕΔ • ྫɿݴޠɹɹɹɹɹɹɹɹɹɹɹɹɹ Λೝࣝ͢ΔΦʔτϚτϯ • ྆ऀͷҧ͍͸ʁ q1 L = {filj|i 1, j 0}
14. ܾఆੑ༗ݶΦʔτϚτϯʁඇܾఆੑ༗ݶΦʔτϚτϯʁ • ඇܾఆతͳϞσϧͷ΄͏͕ঢ়ଶભҠਤ͕௚ײతʹ͔͚Δ • ͔͠͠ɼ࣮ࡍʹ͸ܭࢉػͳͲͷ಺෦Ͱ͸ଟ͘ͷ৔߹ܾఆతͳϞσϧ͕࢖ΘΕΔ • ͳͥʁ • ܾఆੑ༗ݶΦʔτϚτϯ͸౳Ձͳඇܾఆੑ༗ݶΦʔτϚτϯ͕ඞͣଘࡏ͢Δ • ػցʹͱͬͯ͸ܾఆੑ༗ݶΦʔτϚτϯͷ΄͏͕ॲཧ͠΍͍͢ • ඇܾఆੑ༗ݶΦʔτϚτϯ͸ਓ͕ݟͯΘ͔Γ΍͍͢ʢ௚ײతʣ • ఆٛ͢Δͱ͖͸ඇܾఆੑ༗ݶΦʔτϚτϯɼ࣮૷͢Δͱ͖͸ܾఆੑ༗ݶΦʔτϚτϯʹ ม׵͢Ε͹ྑͦ͞͏ʢม׵ͷΞϧΰϦζϜʣ
15. ۭಈ࡞Λ࣋ͭ༗ݶΦʔτϚτϯ • ݴޠɹɹɹɹɹɹɹɹɹɹɹɹɹΛೝࣝ͢ΔΦʔτϚτϯΛߟ͑Δ • Θ͔Γʹ͍͘… • શ෦डཧঢ়ଶ… L = {aibj|i 0, j 0} q0 b a b 1. ۭಈ࡞Λ࣋ͨͳ͍ܾఆੑ༗ݶΦʔτϚτϯ q1
16. ۭಈ࡞Λ࣋ͭ༗ݶΦʔτϚτϯ • ݴޠɹɹɹɹɹɹɹɹɹɹɹɹɹΛೝࣝ͢ΔΦʔτϚτϯΛߟ͑Δ • ۭه߸ɹΛߟ͑Δ͜ͱͰ౳Ձͳ௚ײతʢʁʣΦʔτϚτϯ͕࡞ΕΔ • 0ճҎ্ͷ܁Γฦ͠Λߟ͑Δࡍʹศར • ਖ਼نදݱͰ׆༂ L = {aibj|i 0, j 0} q0 b a b 1. ۭಈ࡞Λ࣋ͨͳ͍ܾఆੑ༗ݶΦʔτϚτϯ q1 q0 a b 2. ۭಈ࡞Λܾ࣋ͭఆੑ༗ݶΦʔτϚτϯ q1 a = a = a
17. ୈ1ষ: ΦʔτϚτϯͱ͸ ୈ2ষ: ༗ݶΦʔτϚτϯ ୈ3ষ: ༗ݶΦʔτϚτϯͷݶք ୈ4ষ: ਖ਼نදݱ
18. ༗ݶΦʔτϚτϯͷݶք • ༗ݶΦʔτϚτϯͰ͸ೝࣝ͢Δ͜ͱ͕Ͱ͖ͳ͍ݴޠ͕ଘࡏ͢Δ • ྫ1ɿճจ͔ΒͳΔݴޠ • { “ͱ·ͱ”, “͚ͨ΍Ϳ΍͚ͨ”, “͠ΜͿΜ͠”, … } • ྫ2ɿಉ਺ճ܁Γฦ͢ه߸͔ΒͳΔݴޠ • {“ab”, “aabb”, “aaabbb”, …} • ϓογϡμ΢ϯΦʔτϚτϯɼνϡʔϦϯάϚγϯ͕ղܾ L = {aibi|i 1}
19. ݴޠLΛडཧ͢ΔΦʔτϚτϯʁ • ݴޠ • ΦʔτϚτϯ1͸ʁ • “abb”, “abbb”, …΋डཧͯ͠͠·͏ • ఆٛʹໃ६ • ΦʔτϚτϯ2͸ʁ • ΞΠσΞɿ2*i + 1ݸͷঢ়ଶΛ࣋ͭ • i͸1Ҏ্ͷࣗવ਺ • ༗ݶͰ͋Δ͜ͱʹໃ६ L = {aibi|i 1} q0 q1 q2 a b b a 1. ݴޠLΛडཧ͢ΔΦʔτϚτϯʁ 2. ݴޠLΛडཧ͢ΔΦʔτϚτϯʁ … … a a a a b b b b b b b
20. ͳͥ༗ݶΦʔτϚτϯͰ͸डཧͰ͖ͳ͍ݴޠ͕͋Δʁ • ௚ײతʹ͸ʮաڈͷ৘ใΛ͓֮͑ͯ͘͜ͱ͕Ͱ͖ͳ͍͔Βʯ • ͋Δঢ়ଶʹ͓͍ͯɼաڈͷঢ়ଶͷܥྻ͕෼͔Ε͹…. • هԱ૷ஔ͕ඞཁ • ϓογϡμ΢ϯΦʔτϚτϯɼνϡʔϦϯάϚγϯ͕͜ͷ՝୊Λղܾ͢Δ
21. ୈ1ষ: ΦʔτϚτϯͱ͸ ୈ2ষ: ༗ݶΦʔτϚτϯ ୈ3ষ: ༗ݶΦʔτϚτϯͷݶք ୈ4ষ: ਖ਼نදݱ
22. ਖ਼نදݱͱ͸ʁ • ϓϩάϥϛϯάݴޠΛ࢖ͬͯςΩετΛॲཧ͢Δͱ͖ʹ࢖͏ • ಛఆͷ৚݅Λຬͨ͢ه߸ྻΛݟ͚ͭΔ • /^[a-z]*-[0-9]*/ Έ͍ͨͳ΍ͭʢRubyʣ • ʢ”0ճҎ্ͷจࣈͷ܁Γฦ͠”-“0ճҎ্ͷ਺ࣈͷ܁Γฦ͠”ʣ • ྫɿ”potato-1”, “tomato-2”, “carrot-3” • *ͱ͔࢖ͬͯΔ͚Ͳ͜ΕͬͯԿʁ
23. ਖ਼نදݱͷ४උ • *ɿ0ճҎ্ͷ܁Γฦ͠ɿελʔดแ • +ɿ1ճҎ্ͷ܁Γฦ͠ • ()ɿه߸ྻΛ1ͭͷه߸ͱΈͳ͢ʢؙׅހɼύʔϨϯʣ • |ɿ۠੾ΒΕͨه߸ͷ೚ҙͷ1ه߸Λද͢ʢॎ๮ɼόʔςΟΧϧόʔʣ • ྫɿ(ab)|c -> ab, c
24. ਖ਼نදݱͷ४උ - ελʔดแ • ه߸ͷू߹Λɹͱ͢Δ • ྫɿ • ɹͷελʔดแɹɹ͸… ۭจࣈྻɹͱɹɹʹؚ·ΕΔه߸Λ࢖ͬͯ࡞ΕΔ͋ΒΏΔه߸ྻ͔ΒͳΔແݶू߹ ʢɹɹ ʹؚ·ΕΔه߸Λ࢖ͬͯ࡞ΕΔ͋ΒΏΔه߸ྻ͔ΒͳΔແݶू߹ɿɹɹ ʣ 0ճҎ্ͷ܁Γฦ͠ = {a, b} = { , a, b, aa, ab, ba, bb, aaa, . . . } + = {a, b} 0 = { } = i=0 i + = i=1 i
25. ਖ਼نදݱͷ४උ - ࿈઀ • ɹɹɹɹɹɹɹɹɹͷͱ͖ • ࿈઀ • ݴޠɹ ͱݴޠɹ ͷ࿈઀ • ಛघͳ৔߹ • ۭจࣈྻͷΈ͔ΒͳΔू߹ɹ , ۭू߹ x = ”aa”, y = ”bb” xy = ”aabb” L1 L2 L1 L2 = {xy|x L1 , y L2 } L1 L = L1 , L1 L = L L ۭू߹ͱͷ࿈઀͸੒ཱ͠ͳ͍
26. ਖ਼نදݱͱ౳Ձͳ༗ݶΦʔτϚτϯ • ઌ΄Ͳ֬ೝͨ͠ҎԼͷૢ࡞ʢʁʣΛߦ͏༗ݶΦʔτϚτϯ • ਖ਼نදݱͱ౳ՁͳΦʔτϚτϯ • ૢ࡞ʢʁʣ • ελʔดแ • ؙׅހ • ॎ๮ • ࿈઀ ਤɿ͸͡ΊֶͯͿ ΦʔτϚτϯͱݴޠཧ࿦ΑΓ
27. ࢀߟࢿྉ • ౻ݪڿ޺. ͸͡ΊֶͯͿΦʔτϚτϯͱݴޠཧ࿦. ৿๺ग़൛, 2015, 176p. • ͜ͷษڧձͰಡΉ͜ͱʹͳ͍ͬͯΔຊ • ෋ాӻ࣍, ԣ৿و. ΦʔτϚτϯɾݴޠཧ࿦. ୈ2൛, ৿๺ग़൛, 2013, 214p. • ษڧձͰಡΜͰΔຊΑΓৄ͍͠
28. ͓·͚ɿू߹ͱ͸
29. ू߹ͱ͸Կ͔ • ֬ఆ͞Εͨର৅෺ͷू·Γ • ɹɹɹ͸ू߹ • ू߹ͷཁૉʹ͸ॏෳ͸ೝΊΒΕͳ͍ • ɹɹɹ͸ू߹Ͱ͸ͳ͍ • ू߹ʹ͸ೋछྨ͋Δ • ༗ݶू߹ʢfinite setʣɿཁૉ͕༗ݶݸ • ແݶू߹ʢinfinite setʣɿཁૉ͕ແݶݸ
30. ू߹ʹؔ͢Δه๏ • ू߹ͷఆٛํ๏ʹ͸2छྨ͋Δ • ֎Ԇతఆٛɿ • ू߹ͷཁૉΛྻڍ͢Δ͜ͱͰू߹Λఆٛ • ແݶू߹Λهड़Ͱ͖ͳ͍ • ಺แతఆٛɿ • ू߹ͷཁૉ͕ຬͨ͢ੑ࣭Λࣔ͢͜ͱͰू߹Λఆٛ
31. ू߹ʹؔ͢Δه๏ • ͋Δಛఆͷཁૉ͕͋Δಛఆͷू߹ʹؚ·Ε͍ͯΔ͔ • , • ͋Δಛఆͷू߹͕͋Δಛఆͷू߹ʹؚ·Ε͍ͯΔ͔ • ɹɹɹ ʢ෦෼ू߹ʣ • ͔ͭAͱB͕ҟͳΔू߹ͷͱ͖: ʢਅ෦෼ू߹ʣ • ఆٛ͞ΕΔԋࢉ • ࿨ • ࠩ • ੵ A B U a A a / A B A B A B A
32. ͓·͚ɿζϯυίΩϤγΛडཧ͢Δ༗ݶΦʔτϚτϯ
33. ζϯυίΩϤγΛडཧ͢Δܾఆੑ༗ݶΦʔτϚτϯ ΩϤγ * • https://gist.github.com/himkt/ef310672b6918288cadff1ba0a06061b q0 q4 q3 q2 q5 q6 q1 ζϯ ζϯ ζϯ ζϯ υί ΩϤγ
34. ζϯυίΩϤγΛडཧ͢Δܾఆੑ༗ݶΦʔτϚτϯ ΩϤγ * • https://gist.github.com/himkt/ef310672b6918288cadff1ba0a06061b ζϯ ζϯ ζϯ ζϯ υί ΩϤγΛೖྗ q0 q4 q3 q2 q5 q6 q1 ζϯ ζϯ ζϯ ζϯ υί ΩϤγ
35. ζϯυίΩϤγΛडཧ͢Δܾఆੑ༗ݶΦʔτϚτϯ ΩϤγ * • https://gist.github.com/himkt/ef310672b6918288cadff1ba0a06061b q0 q4 q3 q2 q5 q6 q1 ζϯ ζϯ ζϯ ζϯ υί ΩϤγ ζϯ ζϯ ζϯ ζϯ υί ΩϤγΛೖྗ
36. ζϯυίΩϤγΛडཧ͢Δܾఆੑ༗ݶΦʔτϚτϯ ΩϤγ * • https://gist.github.com/himkt/ef310672b6918288cadff1ba0a06061b q0 q4 q3 q2 q5 q6 q1 ζϯ ζϯ ζϯ ζϯ υί ΩϤγ ζϯ ζϯ ζϯ ζϯ υί ΩϤγΛೖྗ
37. ζϯυίΩϤγΛडཧ͢Δܾఆੑ༗ݶΦʔτϚτϯ ΩϤγ * • https://gist.github.com/himkt/ef310672b6918288cadff1ba0a06061b q0 q4 q3 q2 q5 q6 q1 ζϯ ζϯ ζϯ ζϯ υί ΩϤγ ζϯ ζϯ ζϯ ζϯ υί ΩϤγΛೖྗ
38. ζϯυίΩϤγΛडཧ͢Δܾఆੑ༗ݶΦʔτϚτϯ ΩϤγ * • https://gist.github.com/himkt/ef310672b6918288cadff1ba0a06061b q0 q4 q3 q2 q5 q6 q1 ζϯ ζϯ ζϯ ζϯ υί ΩϤγ ζϯ ζϯ ζϯ ζϯ υί ΩϤγΛೖྗ
39. ζϯυίΩϤγΛडཧ͢Δܾఆੑ༗ݶΦʔτϚτϯ ΩϤγ * • https://gist.github.com/himkt/ef310672b6918288cadff1ba0a06061b q0 q4 q3 q2 q5 q6 q1 ζϯ ζϯ ζϯ ζϯ υί ΩϤγ ζϯ ζϯ ζϯ ζϯ υί ΩϤγΛೖྗ
40. ζϯυίΩϤγΛडཧ͢Δܾఆੑ༗ݶΦʔτϚτϯ ΩϤγ * • https://gist.github.com/himkt/ef310672b6918288cadff1ba0a06061b q0 q4 q3 q2 q5 q6 q1 ζϯ ζϯ ζϯ ζϯ υί ΩϤγ ζϯ ζϯ ζϯ ζϯ υί ΩϤγΛೖྗ
41. ζϯυίΩϤγΛडཧ͢Δඇܾఆੑ༗ݶΦʔτϚτϯ q0 q3 q2 q1 ΩϤγ υί ζϯ ζϯ