正規演算

$A,B$ を言語とする。正規演算とは、以下のように定義された和集合演算、連結演算、スター演算のいずれかである

• 和集合演算
  • $A\cup B=\{x\mid x\in A\vee x\in B\}$
• 連結演算
  • $A\circ B=\{xy\mid x\in A\wedge y\in B\}$
• スター演算
  • $A^{\ast }=\bigcup _{k\ge 0}{A}^k$
  • ただし、$A^0=\{\epsilon \}$、$A^{k+1}=A^k\circ A$ とする