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

• アルファベットΣ上の文章: Σの記号を重複を許して並べたもの. 記号列や列とも呼ぶ.
• 列の長さ: その列に含まれる記号の個数, 列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, …\}$のように省略して書くしかない.