オートマトンと言語理論のまとめ

有限オートマトン

• オートマトンで登場する記号について
• 決定性有限オートマトン (DFA)と非決定性有限オートマトン (NFA)について
• NFAからDFAへの変換（部分集合構成法）
• DFAとNFAの等価性
• 状態の同値関係
• オートマトンの簡単化

形式言語

• 言語の定義と操作（連結、反転、補集合）
• 正規文法について
• 文脈自由文法について
• 文脈依存文法について
• 線形拘束オートマトン

正規言語と正規表現

• 正規言語の定義
• 正規表現の基本構文
• 正規表現とオートマトンの対応

文脈自由言語

• 文脈自由文法について
• 文脈自由言語とオートマトン

ポンピング補題

• 正規言語に対するポンピング補題
• 文脈自由言語に対するポンピング補題