計算理論の基礎(正規言語) part2

[計算理論]正規言語

正規演算

正規演算とはAとBを言語とした場合に、以下で定義する３つの演算のいずれかを指す。
・和集合演算(union)
\[ A \cup B = \{ x | x \in A または x \in B \} \]
・連結演算(conncatenation)
\[A \circ B = \{xy | x \in A かつ y \in B \ \]
・スター演算子(star)
\[ A^* = \{x_1, x_2, ... , x_k | k \geq 0であり、かつ各々の x_i に対して、x_i \in A \} \]

閉じている

・Nが乗算x, yについて、積x × y もNの要素であるとき、「Nが乗算に関して閉じている」という。

閉じている：その集まりの要素への結果が、その集まりに含まれるものとなる。