REG - formallang.memo

Regular Language

Definition (or Equals-to)

• DFAで受理
• NFAで受理
• AFAで受理
• 左線形文法
• 右線形文法
• 有限モノイドへのhomの引き戻し
• 文字によるleft-quotient closureが有限
• 有限言語を全て含み∪と*と・で閉じた最小のクラス
• DSPACE(O(1))
• NSPACE(O(1))
• DSPACE(o(log log n))
• MSO
• modal-μ

Closure Property

• REG ∪ REG ⊆ REG
• REG ∩ REG ⊆ REG
• ￢REG ⊆ REG
• REG* ⊆ REG
• REG+ ⊆ REG
• REG . REG ⊆ REG
• hom(REG) ⊆ REG
• ehom(REG) ⊆ REG
• hom^-1(REG) ⊆ REG
• REG／REG ⊆ REG
• REG＼REG ⊆ REG