有限オートマトンMは
状態の有限集合　Q　（≠φ）,
入力アルファベット　Σ,
状態遷移関数　δ：Q×Σ→Q,
初期状態　q₀　（∈Q）,
受理状態の集合　F　（⊆Q）
によって規定される。

　状態遷移関数　δ：Q×Σ→Q　とは？
　Q×Σ＝{(q,x)｜q∈Q,x∈Σ}だから、この部分は「ある状態qにある文字xを組み合わせた」ものだ。それを変化後の状態に対応させる。

　例：Q＝{出勤前,定時出勤,遅刻,欠勤}、Σ＝{0,1,2}としよう。ちなみにΣの数字は前夜に飲みに行った店の数を表す。初期状態は出勤前。前夜飲みに行っていなければ定時に出勤、１軒飲みに行くと遅刻し、２軒飲みに行った場合は二日酔いで欠勤。

　うむ。表にすると考えが浅くて漏れているところがよくわかるな。
　初期状態以外のときに0,1,2が与えられたらどう解釈するか…当日の行動が決まった後で、その原因となった昨夜の行動を与えられても変わらないと考えるのが妥当だろう。

　遅刻しちゃった後で「昨日は全然飲んでないじゃん（0）」などと言われても遅刻は遅刻。well-defined？　図にするとこんな感じか。

受理状態は２重の輪で表す。

　つまり受理状態の集合F＝{定時出勤,遅刻,欠勤}。

定理1.16
X⊆Σ^＊が正則集合ならばXの商　x\X　（x∈Σ^＊）のうち相異なるものは有限個である。

　証明略。

定理1.18
X∈Σ^＊が正則集合ならば、任意の語zによるXの商z\Xは正則集合である。

　証明略。

　除算も基本的な演算の一つだ、ということを覚えておこう。

任意の集合X⊆Σ^＊および語y∈Σ^＊に対して
y\X＝{z∈Σ^＊｜yz∈X}
とおき、これをXのyによる左からの商とよぶ。

　例：ひらがな語Σ^＊＝{あ,あのね,いやだなあ,うん,…}の部分集合として、X＝{「あ」で始まるひらがな語}を考える。Xは「いやだなあ」「うん」などを含まないが、「あ」「あのね」などを含む。このXを「あ」で割ってみる。
　「あ」・z∈Σ^＊となるようなz、とは、頭に「あ」をくっつけると、「あ」を含むひらがな語になる、ということだ。当たり前だ！　例が良くない。

　例：ひらがな語Σ^＊＝{あ,ああ,…,あおもり,おおもり,…}の部分集合として、X＝{都道府県名}を考える。Xは「あ」「ああ」「おおもり」などを含まないが、「あいち」「あおもり」など47の元を含む。このXを「あ」で割ってみる。
　「あ」・z∈Σ^＊となるようなz、とは、頭に「あ」をくっつけると、都道府県名になる、ということだ。つまり47都道府県名のうち、「あ」で始まる「あおもり」「あきた」「あいち」（だけ？）から、「あ」を除いた、「おもり」「きた」「いち」がzである資格がある。
　この場合、「あ」\{都道府県名}＝{「おもり」,「きた」,「いち」}　というわけだ。

　商（の性質）に、割る方も割られる方も痕跡が残らないのが、いまいち直感的に理解しにくい。
　…と思ったが、そんなことはないな。除算だから逆演算として積を考えれば納得だ。両辺に「あ」を掛けてこんな感じ。イコールではないが。
　{都道府県名}　⊇　「あ」・{「おもり」,「きた」,「いち」}

　いかにも帰納法が使えそうな感じの定義である。あれ？　ε∈Σ^＊だけど、文字としてΣに含まれているわけではないから、{ε}は正則集合じゃないんだね…。

正則集合を定義するのに用いた三つの演算∪,・,＊を正則演算、正則集合を先の定義（１）～（３）どおりにφと{a}（a∈Σ）と正則演算をつかって表したものをその集合の正則表現とよぶ。

　例：{「あ」}、{「い」}は正則集合だから、あ^＊＝{ε,あ,ああ,あああ,…}、い^＊＝{ε,い,いい,いいい,…}も正則集合で、(あ^＊・い^＊)∪(い^＊・あ^＊)∪…＝{ε,あ,い,あい,いあ,ああい,…}＝{あ,い}^＊も正則集合。
　くっつけたりならべかえたり、ふつうの操作で作れる集合は正則と考えてよさそう。ところが、無理数同様に濃度は正則でない集合の方がはるかに濃い（多い）。

　1-2.可換な語…は飛ばす。初学者は飛ばしてよいと前書きにあった。

語に対する連接をもとに言語に対する連接演算を
XY＝{xy｜x∈X,y∈Y}　（X,Y⊆Σ^＊）
によって定義する。とくに空集合φおよび空語のみからなる集合{ε}については
Xφ＝φ＝φX,
X{ε}＝X＝{ε}X

　空集合の場合がなかなか納得できなかった。Xφ＝X＝φX の誤植かと思ったほど。
　実際はもちろんXφ＝φで正しい。定義により、Xφ＝{xy｜x∈X,y∈φ}だが、y∈φとなるyは存在しない（φは空語εすら含まないから）。したがって、このようなxyという元は存在しない。Xφ＝{存在しない元の集合}といっているのだから、すなわち＝φ（空集合）だ。

　φのフォントが気に入らないな。font-familyを指定すればいいか。
　φ　←style=”font-family:ＭＳ ゴシック;”にしてみた。
　φ　←オイラーフォントが使えるといいが。

X⁰＝{ε}, Xⁱ⁺¹＝XX とおき、
X^＊＝X⁰∪X¹∪X²∪X³∪…
X^＋＝　　X¹∪X²∪X³∪…
とおく。

　X^＊は空語を含む語（1文字の語でもよい）の集合、X^＋は1文字以上の語の集合（空語は含まない）。

定義：Σ上の語x,yに対して、^∃z∈Σ^＊｜y＝xz　であるとき、xはyの接頭語であるといい、x≦yで表す。

　本書では「≦」ではなく、「＜」の下の斜線だけが2重になった記号を使っているが、自然数の大小関係「≦」でもその記号を用いているので、単にフォントの違い（あるいは方言）と考えることにした。

　自然言語については、一般には、この定義のような関係だと「xはzの接頭語である」と言うように思う。
　例：「restart」の「re」は「start」の接頭語（？）

　「yはxで始まる語である」という感じのほうが理解しやすい。
　例：「restart」は「re」で始まる語である

≦はΣ^＊上の半順序である。

　半順序とは、^∀x,^∀y≦Σ^＊に対して、x≦y or y≦x　のどちらかが成り立つ…わけではないが、次のような順序関係は満たす関係のこと。

1. x≦x
2. x≦y　and　y≦x　⇒　x＝y
3. x≦y　and　y≦z　⇒　x≦z

　反射律、対称律（ちょっと違うか）、推移律っぽい。

定義：Σ＝{a,b}上の語x,yの間に、「x≦y」、または、「^∃z∈Σ^＊｜za≦x　and　zb≦y」であるとき、辞書式順序でxはy以下といい、x ≦_lex y と書く。

　辞書のように昇順で並べるとxよりもyの方が後ということだろう。

　「x≦y」つまり「yがxで始まる語である」場合は簡単にわかる。例：x＝aab,y＝aabbabab。そりゃあxが先だろう。
　もう一方の場合をz＝aabbで考えてみよう。za＝aabba,zb＝aabbbだ。xがza始まりの語であり、yがzb始まりの語であるということは、x＝aabba＊＊＊,y＝aabbb＊＊＊で、すでに5文字目で辞書の順番が決まり、以後の＊＊＊部分は順番に影響しないわけだ。
　なるほど辞書式である。

問1.1　h:Σ^＊→Γ^＊　が準同型写像のとき
h(xy)＝h(x)h(y)　（x,y∈Σ^＊）
であることをyの長さに関する帰納法で証明せよ。

Read more…

定義：Σ^＊の部分集合を「言語」という。

　それはさておき。

Σ＝{a}のとき、Σ^＊＝{a}^＊と自然数の集合Nは1対1に対応付けられる。

　{a}^＊とは、{ε,a,aa,aaa,…}のことだ。N＝{0,1,2,3,…}と対応するのは自然。

　ここで言ってる写像は何の条件もないので、別に1対1でもontoでもないはずだ。アルファベット「日本語のひらがな」「日本語のカタカナ」を考えよう。ひらがな文字の集合からカタカナ語の集合（「日本語のカタカナ」*）への写像hを50音順の対応としよう。つまり、あ→ア,い→イ,…,ん→ン、という写像だ（カタカナ語の集合には「ア」「アノネ」「アンタバカネ」「イ」などを含むが、「アノネ」「アンタバカネ」などの語に写ってくるひらがな文字はないことにする）。

　アルファベットにはεを含まないようだ（暗黙？）が、アルファベット上のすべての語の集合にはεを含むので、Σ^＊からの写像に定義を拡張するため「h(ε)＝ε」という設定が必要だ。

　もうひとつの拡張設定をひらがな･カタカナの例で考える。
　x∈Σ^＊,a∈Σに対する「xa」とは、「ひらがな語」と「ひらがな」をつなげたモノ、たとえば「あ・い」、「あのね・え」、「きゅうたろうは・ね」などだ。これに対する写像を、後ろから一文字ずつばらして適用するというわけだ。
　例：h(あい)＝h(あ)h(い)＝「ア」「イ」＝「アイ」、h(あのねえ)＝h(あのね)h(え)＝…＝h(あ)h(の)h(ね)h(え)＝「アノネエ」
　たしかにこれで文字の集合から語の集合への写像を、語の集合から語の集合への写像に拡張している。

　ここではhをintoな写像として考えたが、べつにintoなものをontoに拡張したわけではない。あいかわらず、「アノネ」「アンタバカネ」などの語に写ってくるひらがなはないかもしれない。いや、まあこの例だと実際にはある（もちろん「あのね」→「アノネ」、「あんたばかね」→「アンタバカネ」）んだけど。
　ローマ字とカナで例を作った方がよかったかな。

定義：Σ上の語x＝a₁a₂…a_n,y＝b₁b₂…b_mを続けてできる語a₁a₂…a_nb₁b₂…b_mをxとyの連接（concatenation）、または積とよび、xyと書く。

　そういえば、Excelにおいて文字列を連結する関数は=concatenate(A1,B1)だったかな。

連接は結合法則
x(yz)＝(xy)z　(x,y,z∈Σ)
を満たす。したがって通常、括弧を省略してxyzのように書く。

定義：xの冪とはxⁿ＝xx…x　（n個の連接）
x⁰=ε,x¹=x

　この辺はかんたんに理解できるだろう。
　例：「あ」³＝「あああ」、「あ」⁰＝「」

　ちなみに上の2.の条件「x∈X,a∈Σ　⇒　xa∈X」は、任意の、ということだと思う。「^∀x∈X,^∀a∈Σ　⇒　xa∈X」
　群は覚えてるけど、半群ってなんだっけ。群の演算に関して交換法則を必ずしも満たさない、ってことかな。

電子計算機基礎講座11「オートマトンの理論」／小林孝次郎・高橋正子　を読み解く。抽象的な思考だけではついていけないので、卑近な例をあげて読んでいく。本文からの引用はblockquoteで示す。要約した定義などのメモはそのまま本文中に記すが、blockquoteと似た表記にする。

定義：アルファベットΣとは、有限個の文字からなる空でない集合である。

　例：「日本語のひらがなの集合」は有限の「あ」「い」「う」などの集合なので、アルファベットだ。

定義：アルファベットΣから重複を許して有限個の元をとりだし1列に並べたものをΣ上の語（または文字列）という。

　例：「あ」「あい」「あれまあ」などはアルファベット「日本語のひらがな」上の語である。
　疑問：重複を許さない場合は語とは言わないのか？

Σ上の語w=a₁a₂…a_n（a₁,a₂,…,a_n∈Σ）に対し、nをその長さとよび、記号|w|で表す。

　さまざまなプログラミング言語でいう文字列のlengthと同じだね。