Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
形式言語勉強会(第2回) - 有限オートマトン
Search
himkt
July 12, 2016
Science
0
170
形式言語勉強会(第2回) - 有限オートマトン
形式言語勉強会 #2 @春日エリアの資料です.
himkt
July 12, 2016
Tweet
Share
More Decks by himkt
See All by himkt
Linformer: paper reading
himkt
0
530
RoBERTa: paper reading
himkt
1
350
NLP SoTA 勉強会 / ner_2019
himkt
2
1.4k
自然言語処理 @ クックパッド / nlp at cookpad
himkt
1
520
Interpretable Machine Learning 6.3 - Prototypes and Criticisms
himkt
2
160
ニューラル固有表現抽出 / Neural Named Entity Recognition
himkt
3
740
ニューラル固有表現抽出器を実装してみる / PyNER
himkt
6
2.1k
Spacyでお手軽NLP / NLP with spacy
himkt
0
1k
Deep Learning Book 10その2 / deep learning book 10 vol2
himkt
2
190
Other Decks in Science
See All in Science
機械学習 - 授業概要
trycycle
PRO
0
230
データベース12: 正規化(2/2) - データ従属性に基づく正規化
trycycle
PRO
0
960
02_西村訓弘_プログラムディレクター_人口減少を機にひらく未来社会.pdf
sip3ristex
0
590
データベース08: 実体関連モデルとは?
trycycle
PRO
0
930
Quelles valorisations des logiciels vers le monde socio-économique dans un contexte de Science Ouverte ?
bluehats
1
470
Transport information Geometry: Current and Future II
lwc2017
0
180
生成AIと学ぶPythonデータ分析再入門-Pythonによるクラスタリング・可視化をサクサク実施-
datascientistsociety
PRO
4
1.7k
Trend Classification of InSAR Displacement Time Series Using SAE–CNN
satai
4
550
03_草原和博_広島大学大学院人間社会科学研究科教授_デジタル_シティズンシップシティで_新たな_学び__をつくる.pdf
sip3ristex
0
570
データベース02: データベースの概念
trycycle
PRO
2
890
07_浮世満理子_アイディア高等学院学院長_一般社団法人全国心理業連合会代表理事_紹介資料.pdf
sip3ristex
0
580
Lean4による汎化誤差評価の形式化
milano0017
1
290
Featured
See All Featured
GraphQLとの向き合い方2022年版
quramy
49
14k
CSS Pre-Processors: Stylus, Less & Sass
bermonpainter
358
30k
A Modern Web Designer's Workflow
chriscoyier
695
190k
Art, The Web, and Tiny UX
lynnandtonic
302
21k
Agile that works and the tools we love
rasmusluckow
329
21k
Practical Orchestrator
shlominoach
190
11k
Building an army of robots
kneath
306
46k
How to Create Impact in a Changing Tech Landscape [PerfNow 2023]
tammyeverts
53
2.9k
GitHub's CSS Performance
jonrohan
1031
460k
Navigating Team Friction
lara
189
15k
Into the Great Unknown - MozCon
thekraken
40
2k
Helping Users Find Their Own Way: Creating Modern Search Experiences
danielanewman
29
2.8k
Transcript
༗ݶΦʔτϚτϯͱਖ਼نදݱ ܗࣜݴޠษڧձ #2 @ य़ΤϦΞ himkt <
[email protected]
>
ୈ1ষ: ΦʔτϚτϯͱ ୈ2ষ: ༗ݶΦʔτϚτϯ ୈ3ষ: ༗ݶΦʔτϚτϯͷݶք ୈ4ষ: ਖ਼نදݱ
ୈ1ষ: ΦʔτϚτϯͱ ୈ2ষ: ༗ݶΦʔτϚτϯ ୈ3ষ: ༗ݶΦʔτϚτϯͷݶք ୈ4ষ: ਖ਼نදݱ
ΦʔτϚτϯͱ…ͷલʹܭࢉͱʁ • ܭࢉ͚͕ͩܭࢉͰͳ͍ • “1 + 1” -> “2” •
“aiueo” -> “͍͋͏͓͑” • ίϯϐϡʔλʹ͓͍ͯܭࢉΛ࢘ΔͷCPUͱϝϞϦ • ߏඇৗʹෳࡶ • ΦʔτϚτϯɿʮܭࢉʯΛ࣮ߦ͢ΔֶతϞσϧ • ݪ࢝త͔ͭநత ͜Εܭࢉ ͜Εܭࢉ
ΦʔτϚτϯͱʁ • ೖྗɼग़ྗɼঢ়ଶΛ͍࣋ͬͯΔʢू߹ʣ • ೖྗʹରͯ͠ɼͦͷঢ়ଶʹԠͨ͡ग़ྗΛ͢Δ • ঢ়ଶͷʮભҠʯঢ়ଶͱه߸ΛҾͱͯ͠ঢ়ଶΛग़ྗ͢Δؔ ʹΑͬͯఆٛ͞ΕΔ ྫ: ೖྗ
ग़ྗ ঢ়ଶ q0 q1 q2 1 0 ঢ়ଶɿ·Δ͍ͭɼભҠɿখ͍͞ҹ ʢେ͖͍ҹॳظঢ়ଶʣ f(q0 , 1) = q1 , f(q1 , 0) = q2
ΦʔτϚτϯͷछྨ • ܾఆੑ༗ݶΦʔτϚτϯ • ඇܾఆੑ༗ݶΦʔτϚτϯ • ܾఆੑϓογϡμϯΦʔτϚτϯ • ඇܾఆੑϓογϡμϯΦʔτϚτϯ •
ܾఆੑνϡʔϦϯάϚγϯ • ඇܾఆੑνϡʔϦϯάϚγϯ ෳࡶ ؆ૉ
ୈ1ষ: ΦʔτϚτϯͱ ୈ2ষ: ༗ݶΦʔτϚτϯ ୈ3ষ: ༗ݶΦʔτϚτϯͷݶք ୈ4ষ: ਖ਼نදݱ
༗ݶΦʔτϚτϯ…ͦͷલʹɼݴޠͱʁ • ͋ΔΦʔτϚτϯ͕डཧ͢Δه߸ྻͷू߹Λݴޠͱ͍͏ • ΦʔτϚτϯݴޠΛʮೝࣝʯ͢Δ • ྫ: ݴޠɹɹɹɹɹɹɹɹɹɹɹɹɹ Λೝࣝ͢ΔΦʔτϚτϯ •
“f”, “fl”, “ffl”, “fll”, … • ͜ͷه߸ྻͷू߹͕ݴޠʢ͜ͷ߹ແݶू߹ʣ L = {filj|i 1, j 0}
ܾఆੑ༗ݶΦʔτϚτϯͱʁ • 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 }
ܾఆੑ༗ݶΦʔτϚτϯͱʁ • 3ͭͷू߹ɼ1ͭͷؔɼ1ͭͷཁૉʹΑͬͯߏ͞ΕΔ • ঢ়ଶू߹ɼೖྗه߸ू߹ɼडཧঢ়ଶɼঢ়ଶભҠؔɼॳظঢ়ଶ • ܗࣜతʹɿ • ྫɿݴޠɹɹɹɹɹɹɹɹɹɹɹɹɹ Λೝࣝ͢ΔΦʔτϚτϯ
q0 q1 q2 f l l f M = (Q, , , q0 , F) L = {filj|i 1, j 0}
ʮඇʯܾఆੑ༗ݶΦʔτϚτϯͱʁ • 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 }
ʮඇʯܾఆੑ༗ݶΦʔτϚτϯͱʁ • 3ͭͷू߹ɼ1ͭͷؔɼ1ͭͷཁૉʹΑͬͯߏ͞ΕΔ • ঢ়ଶू߹ɼೖྗه߸ू߹ɼडཧঢ়ଶɼঢ়ଶભҠؔɼॳظঢ়ଶ • ܗࣜతʹɿ • ྫɿݴޠɹɹɹɹɹɹɹɹɹɹɹɹɹ Λೝࣝ͢ΔΦʔτϚτϯ
M = (Q, , , q0 , F) L = {filj|i 1, j 0} q0 f f l q1
ܾఆੑ༗ݶΦʔτϚτϯʁඇܾఆੑ༗ݶΦʔτϚτϯʁ q0 q1 q2 q0 f l f f l
l f 1. ܾఆੑ༗ݶΦʔτϚτϯ 2. ඇܾఆੑ༗ݶΦʔτϚτϯ • ༗ݶΦʔτϚτϯͷঢ়ଶભҠؔೖྗʹରͯ͠ग़ྗ͕Ұҙʹܾ·Δ • ඇܾఆΦʔτϚτϯͷঢ়ଶભҠؔೖྗʹରͯ͠ෳͷग़ྗ͕͋Γ͏Δ • ભҠͷํ͕ෳߟ͑ΒΕΔ • ྫɿݴޠɹɹɹɹɹɹɹɹɹɹɹɹɹ Λೝࣝ͢ΔΦʔτϚτϯ • ྆ऀͷҧ͍ʁ q1 L = {filj|i 1, j 0}
ܾఆੑ༗ݶΦʔτϚτϯʁඇܾఆੑ༗ݶΦʔτϚτϯʁ • ඇܾఆతͳϞσϧͷ΄͏͕ঢ়ଶભҠਤ͕ײతʹ͔͚Δ • ͔͠͠ɼ࣮ࡍʹܭࢉػͳͲͷ෦Ͱଟ͘ͷ߹ܾఆతͳϞσϧ͕ΘΕΔ • ͳͥʁ • ܾఆੑ༗ݶΦʔτϚτϯՁͳඇܾఆੑ༗ݶΦʔτϚτϯ͕ඞͣଘࡏ͢Δ •
ػցʹͱܾͬͯఆੑ༗ݶΦʔτϚτϯͷ΄͏͕ॲཧ͍͢͠ • ඇܾఆੑ༗ݶΦʔτϚτϯਓ͕ݟͯΘ͔Γ͍͢ʢײతʣ • ఆٛ͢Δͱ͖ඇܾఆੑ༗ݶΦʔτϚτϯɼ࣮͢Δͱ͖ܾఆੑ༗ݶΦʔτϚτϯʹ ม͢Εྑͦ͞͏ʢมͷΞϧΰϦζϜʣ
ۭಈ࡞Λ࣋ͭ༗ݶΦʔτϚτϯ • ݴޠɹɹɹɹɹɹɹɹɹɹɹɹɹΛೝࣝ͢ΔΦʔτϚτϯΛߟ͑Δ • Θ͔Γʹ͍͘… • શ෦डཧঢ়ଶ… L = {aibj|i
0, j 0} q0 b a b 1. ۭಈ࡞Λ࣋ͨͳ͍ܾఆੑ༗ݶΦʔτϚτϯ q1
ۭಈ࡞Λ࣋ͭ༗ݶΦʔτϚτϯ • ݴޠɹɹɹɹɹɹɹɹɹɹɹɹɹΛೝࣝ͢ΔΦʔτϚτϯΛߟ͑Δ • ۭه߸ɹΛߟ͑Δ͜ͱͰՁͳײతʢʁʣΦʔτϚτϯ͕࡞ΕΔ • 0ճҎ্ͷ܁Γฦ͠Λߟ͑Δࡍʹศར • ਖ਼نදݱͰ׆༂ L
= {aibj|i 0, j 0} q0 b a b 1. ۭಈ࡞Λ࣋ͨͳ͍ܾఆੑ༗ݶΦʔτϚτϯ q1 q0 a b 2. ۭಈ࡞Λܾ࣋ͭఆੑ༗ݶΦʔτϚτϯ q1 a = a = a
ୈ1ষ: ΦʔτϚτϯͱ ୈ2ষ: ༗ݶΦʔτϚτϯ ୈ3ষ: ༗ݶΦʔτϚτϯͷݶք ୈ4ষ: ਖ਼نදݱ
༗ݶΦʔτϚτϯͷݶք • ༗ݶΦʔτϚτϯͰೝࣝ͢Δ͜ͱ͕Ͱ͖ͳ͍ݴޠ͕ଘࡏ͢Δ • ྫ1ɿճจ͔ΒͳΔݴޠ • { “ͱ·ͱ”, “͚ͨͿ͚ͨ”, “͠ΜͿΜ͠”,
… } • ྫ2ɿಉճ܁Γฦ͢ه߸͔ΒͳΔݴޠ • {“ab”, “aabb”, “aaabbb”, …} • ϓογϡμϯΦʔτϚτϯɼνϡʔϦϯάϚγϯ͕ղܾ L = {aibi|i 1}
ݴޠLΛडཧ͢ΔΦʔτϚτϯʁ • ݴޠ • ΦʔτϚτϯ1ʁ • “abb”, “abbb”, …डཧͯ͠͠·͏ •
ఆٛʹໃ६ • ΦʔτϚτϯ2ʁ • ΞΠσΞɿ2*i + 1ݸͷঢ়ଶΛ࣋ͭ • i1Ҏ্ͷࣗવ • ༗ݶͰ͋Δ͜ͱʹໃ६ 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
ͳͥ༗ݶΦʔτϚτϯͰडཧͰ͖ͳ͍ݴޠ͕͋Δʁ • ײతʹʮաڈͷใΛ͓֮͑ͯ͘͜ͱ͕Ͱ͖ͳ͍͔Βʯ • ͋Δঢ়ଶʹ͓͍ͯɼաڈͷঢ়ଶͷܥྻ͕͔Ε…. • هԱஔ͕ඞཁ • ϓογϡμϯΦʔτϚτϯɼνϡʔϦϯάϚγϯ͕͜ͷ՝Λղܾ͢Δ
ୈ1ষ: ΦʔτϚτϯͱ ୈ2ষ: ༗ݶΦʔτϚτϯ ୈ3ষ: ༗ݶΦʔτϚτϯͷݶք ୈ4ষ: ਖ਼نදݱ
ਖ਼نදݱͱʁ • ϓϩάϥϛϯάݴޠΛͬͯςΩετΛॲཧ͢Δͱ͖ʹ͏ • ಛఆͷ݅Λຬͨ͢ه߸ྻΛݟ͚ͭΔ • /^[a-z]*-[0-9]*/ Έ͍ͨͳͭʢRubyʣ • ʢ”0ճҎ্ͷจࣈͷ܁Γฦ͠”-“0ճҎ্ͷࣈͷ܁Γฦ͠”ʣ
• ྫɿ”potato-1”, “tomato-2”, “carrot-3” • *ͱ͔ͬͯΔ͚Ͳ͜ΕͬͯԿʁ
ਖ਼نදݱͷ४උ • *ɿ0ճҎ্ͷ܁Γฦ͠ɿελʔดแ • +ɿ1ճҎ্ͷ܁Γฦ͠ • ()ɿه߸ྻΛ1ͭͷه߸ͱΈͳ͢ʢؙׅހɼύʔϨϯʣ • |ɿ۠ΒΕͨه߸ͷҙͷ1ه߸Λද͢ʢॎɼόʔςΟΧϧόʔʣ •
ྫɿ(ab)|c -> ab, c
ਖ਼نදݱͷ४උ - ελʔดแ • ه߸ͷू߹Λɹͱ͢Δ • ྫɿ • ɹͷελʔดแɹɹ… ۭจࣈྻɹͱɹɹʹؚ·ΕΔه߸Λͬͯ࡞ΕΔ͋ΒΏΔه߸ྻ͔ΒͳΔແݶू߹
ʢɹɹ ʹؚ·ΕΔه߸Λͬͯ࡞ΕΔ͋ΒΏΔه߸ྻ͔ΒͳΔແݶू߹ɿɹɹ ʣ 0ճҎ্ͷ܁Γฦ͠ = {a, b} = { , a, b, aa, ab, ba, bb, aaa, . . . } + = {a, b} 0 = { } = i=0 i + = i=1 i
ਖ਼نදݱͷ४උ - ࿈ • ɹɹɹɹɹɹɹɹɹͷͱ͖ • ࿈ • ݴޠɹ ͱݴޠɹ
ͷ࿈ • ಛघͳ߹ • ۭจࣈྻͷΈ͔ΒͳΔू߹ɹ , ۭू߹ x = ”aa”, y = ”bb” xy = ”aabb” L1 L2 L1 L2 = {xy|x L1 , y L2 } L1 L = L1 , L1 L = L L ۭू߹ͱͷ࿈ཱ͠ͳ͍
ਖ਼نදݱͱՁͳ༗ݶΦʔτϚτϯ • ઌ΄Ͳ֬ೝͨ͠ҎԼͷૢ࡞ʢʁʣΛߦ͏༗ݶΦʔτϚτϯ • ਖ਼نදݱͱՁͳΦʔτϚτϯ • ૢ࡞ʢʁʣ • ελʔดแ •
ؙׅހ • ॎ • ࿈ ਤɿ͡ΊֶͯͿ ΦʔτϚτϯͱݴޠཧΑΓ
ࢀߟࢿྉ • ౻ݪڿ. ͡ΊֶͯͿΦʔτϚτϯͱݴޠཧ. ग़൛, 2015, 176p. • ͜ͷษڧձͰಡΉ͜ͱʹͳ͍ͬͯΔຊ •
ాӻ࣍, ԣو. ΦʔτϚτϯɾݴޠཧ. ୈ2൛, ग़൛, 2013, 214p. • ษڧձͰಡΜͰΔຊΑΓৄ͍͠
͓·͚ɿू߹ͱ
ू߹ͱԿ͔ • ֬ఆ͞Εͨରͷू·Γ • ɹɹɹू߹ • ू߹ͷཁૉʹॏෳೝΊΒΕͳ͍ • ɹɹɹू߹Ͱͳ͍ •
ू߹ʹೋछྨ͋Δ • ༗ݶू߹ʢfinite setʣɿཁૉ͕༗ݶݸ • ແݶू߹ʢinfinite setʣɿཁૉ͕ແݶݸ
ू߹ʹؔ͢Δه๏ • ू߹ͷఆٛํ๏ʹ2छྨ͋Δ • ֎Ԇతఆٛɿ • ू߹ͷཁૉΛྻڍ͢Δ͜ͱͰू߹Λఆٛ • ແݶू߹Λهड़Ͱ͖ͳ͍ •
แతఆٛɿ • ू߹ͷཁૉ͕ຬͨ͢ੑ࣭Λࣔ͢͜ͱͰू߹Λఆٛ
ू߹ʹؔ͢Δه๏ • ͋Δಛఆͷཁૉ͕͋Δಛఆͷू߹ʹؚ·Ε͍ͯΔ͔ • , • ͋Δಛఆͷू߹͕͋Δಛఆͷू߹ʹؚ·Ε͍ͯΔ͔ • ɹɹɹ ʢ෦ू߹ʣ
• ͔ͭAͱB͕ҟͳΔू߹ͷͱ͖: ʢਅ෦ू߹ʣ • ఆٛ͞ΕΔԋࢉ • • ࠩ • ੵ A B U a A a / A B A B A B A
͓·͚ɿζϯυίΩϤγΛडཧ͢Δ༗ݶΦʔτϚτϯ
ζϯυίΩϤγΛडཧ͢Δܾఆੑ༗ݶΦʔτϚτϯ ΩϤγ * • https://gist.github.com/himkt/ef310672b6918288cadff1ba0a06061b q0 q4 q3 q2 q5
q6 q1 ζϯ ζϯ ζϯ ζϯ υί ΩϤγ
ζϯυίΩϤγΛडཧ͢Δܾఆੑ༗ݶΦʔτϚτϯ ΩϤγ * • https://gist.github.com/himkt/ef310672b6918288cadff1ba0a06061b ζϯ ζϯ ζϯ ζϯ υί
ΩϤγΛೖྗ q0 q4 q3 q2 q5 q6 q1 ζϯ ζϯ ζϯ ζϯ υί ΩϤγ
ζϯυίΩϤγΛडཧ͢Δܾఆੑ༗ݶΦʔτϚτϯ ΩϤγ * • https://gist.github.com/himkt/ef310672b6918288cadff1ba0a06061b q0 q4 q3 q2 q5
q6 q1 ζϯ ζϯ ζϯ ζϯ υί ΩϤγ ζϯ ζϯ ζϯ ζϯ υί ΩϤγΛೖྗ
ζϯυίΩϤγΛडཧ͢Δܾఆੑ༗ݶΦʔτϚτϯ ΩϤγ * • https://gist.github.com/himkt/ef310672b6918288cadff1ba0a06061b q0 q4 q3 q2 q5
q6 q1 ζϯ ζϯ ζϯ ζϯ υί ΩϤγ ζϯ ζϯ ζϯ ζϯ υί ΩϤγΛೖྗ
ζϯυίΩϤγΛडཧ͢Δܾఆੑ༗ݶΦʔτϚτϯ ΩϤγ * • https://gist.github.com/himkt/ef310672b6918288cadff1ba0a06061b q0 q4 q3 q2 q5
q6 q1 ζϯ ζϯ ζϯ ζϯ υί ΩϤγ ζϯ ζϯ ζϯ ζϯ υί ΩϤγΛೖྗ
ζϯυίΩϤγΛडཧ͢Δܾఆੑ༗ݶΦʔτϚτϯ ΩϤγ * • https://gist.github.com/himkt/ef310672b6918288cadff1ba0a06061b q0 q4 q3 q2 q5
q6 q1 ζϯ ζϯ ζϯ ζϯ υί ΩϤγ ζϯ ζϯ ζϯ ζϯ υί ΩϤγΛೖྗ
ζϯυίΩϤγΛडཧ͢Δܾఆੑ༗ݶΦʔτϚτϯ ΩϤγ * • https://gist.github.com/himkt/ef310672b6918288cadff1ba0a06061b q0 q4 q3 q2 q5
q6 q1 ζϯ ζϯ ζϯ ζϯ υί ΩϤγ ζϯ ζϯ ζϯ ζϯ υί ΩϤγΛೖྗ
ζϯυίΩϤγΛडཧ͢Δܾఆੑ༗ݶΦʔτϚτϯ ΩϤγ * • https://gist.github.com/himkt/ef310672b6918288cadff1ba0a06061b q0 q4 q3 q2 q5
q6 q1 ζϯ ζϯ ζϯ ζϯ υί ΩϤγ ζϯ ζϯ ζϯ ζϯ υί ΩϤγΛೖྗ
ζϯυίΩϤγΛडཧ͢Δඇܾఆੑ༗ݶΦʔτϚτϯ q0 q3 q2 q1 ΩϤγ υί ζϯ ζϯ