• 作成:

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

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

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

言語と言語の連接

集合の直積.

スター演算

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

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

正規表現

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

  1. 00
  2. εε
  3. ΣΣに関するαα
  4. R1R_1R2R_2を正規表現として, R1+R2R_1 + R_2 (R1R2)(R_1 ∪ R_2)
  5. R1R_1R2R_2を正規表現として, R1R2R_1 R_2
  6. R1R_1を正規表現として, R1*R_1^*

和集合のスター演算

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