文字列

• アルファベット上の 文字列 とは、そのアルファベットの文字からなる有限列

• 各文字間をカンマで区切らない

  • $\Sigma =\{a,b\}$ のとき、$ababa$ は $\Sigma$ 上の文字列

• 長さ

  • $|w|$
  • $w$ を $\Sigma$ 上の文字列とするとき、$w$ に含まれる文字の数

• 空列 $ϵ$

  • 長さが0の文字列