• 作成日時:
  • 更新日時:

計算理論(正規言語と有限オートマトン)

形式言語における言葉の定義

  • アルファベットΣ上の文章: Σの記号を重複を許して並べたもの.記号列とも呼ぶ.
  • 列の長さ: その列に含まれる記号の個数,列xの長さを|x|と書く.また長さ0の列を空列と呼び,εで表す.
  • 列xとyの連接とは,列xの後ろにyをつなげた列のことでxyと書く.またxxを\(x^2\)と書くこともある.
  • 列xのあるいは逆語とは,列xを逆から並べた列のことで,\(x^R\)と書く.例えば\(x = 110\)のとき,\(x^R = 011\)である.

言語と言語の連接

集合の直積.

スター演算

\(L = \{a\}\)のとき,\(L^* = L^0 ∪ L^1 ∪ … = \{ε, a, aa, aaa, aaaa, …\}\)である.

\(L = \{a, bb\}\)のとき,\(L^* = \{ε, a, bb, aa, bbbb, abb, bba, aaa, bbbbbb, aabb, abbbb, …\}\)である.

正規表現

コンピュータで使われる正規表現とは異なる.

  1. \(0\)
  2. \(ε\)
  3. \(Σ\)に関する\(α\)
  4. \(R_1\)\(R_2\)を正規表現として,\(R_1 + R_2\) \((R_1 ∪ R_2)\)
  5. \(R_1\)\(R_2\)を正規表現として,\(R_1 R_2\)
  6. \(R_1\)を正規表現として,\(R_1^*\)

和集合のスター演算

\((a + b)^*\)のようなものを集合の記法で表すことはできない.むしろそういったものを表すのが正規表現.これをばらすには\(\{ε, a, ab, aa, aab, …\}\)のように省略して書くしかない.