定義：Σ上の語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文字目で辞書の順番が決まり、以後の＊＊＊部分は順番に影響しないわけだ。
　なるほど辞書式である。