電子計算機基礎講座11「オートマトンの理論」/小林孝次郎・高橋正子 を読み解く。抽象的な思考だけではついていけないので、卑近な例をあげて読んでいく。本文からの引用はblockquoteで示す。要約した定義などのメモはそのまま本文中に記すが、blockquoteと似た表記にする。
定義:アルファベットΣとは、有限個の文字からなる空でない集合である。
例:「日本語のひらがなの集合」は有限の「あ」「い」「う」などの集合なので、アルファベットだ。
定義:アルファベットΣから重複を許して有限個の元をとりだし1列に並べたものをΣ上の語(または文字列)という。
例:「あ」「あい」「あれまあ」などはアルファベット「日本語のひらがな」上の語である。
疑問:重複を許さない場合は語とは言わないのか?
Σ上の語w=a1a2…an(a1,a2,…,an∈Σ)に対し、nをその長さとよび、記号|w|で表す。
さまざまなプログラミング言語でいう文字列のlengthと同じだね。
定義:
- 文字を一つも含まない「空語」をεで表す
- Σ上のすべての語の集合をΣ*で表す
- 長さ1以上の語の集合をΣ+で表す
Σ+=Σ*-{ε}、←この「-」はただの集合の演算
2 Comments