応用情報（AP）
オートマトンと形式言語
オートマトン
オートマトンとは、入力を受け取りながら状態を変化させ、決められた動作を行う仕組みを表した数学的モデルです。
Huneyの用語辞典
用語辞典
わからない言葉を、短く、やさしく確認できます。
学習順
応用情報（AP）
オートマトンと形式言語
状態遷移
状態遷移とは、現在の状態から入力や条件に応じて別の状態へ移動することです。オートマトンの基本となる考え方です。
応用情報（AP）
オートマトンと形式言語
有限オートマトン
有限オートマトンとは、有限個の状態を持ち、入力を読みながら状態遷移を行うオートマトンです。
応用情報（AP）
オートマトンと形式言語
DFA
DFAとは、現在の状態と入力が決まれば、次の状態が必ず1つに決まる有限オートマトンです。
応用情報（AP）
オートマトンと形式言語
NFA
NFAとは、同じ状態と入力に対して複数の遷移先を持つことができる有限オートマトンです。
応用情報（AP）
オートマトンと形式言語
ε遷移
ε遷移とは、入力記号を読み取らずに、ある状態から別の状態へ移動する状態遷移です。
応用情報（AP）
オートマトンと形式言語
正規言語
正規言語とは、有限オートマトンによって受理できる形式言語です。正規表現でも表現できます。
応用情報（AP）
オートマトンと形式言語
正規表現
正規表現とは、文字列のパターンを一定の記法で表現する方法です。有限オートマトンと同じ正規言語を表現できます。
応用情報（AP）
オートマトンと形式言語
形式言語
形式言語とは、決められた記号と規則に従って作られる文字列の集合です。
応用情報（AP）
オートマトンと形式言語
形式文法
形式文法とは、形式言語に含まれる文字列をどのようなルールで生成するかを定めたものです。
応用情報（AP）
オートマトンと形式言語
生成規則
生成規則とは、形式文法において、ある記号を別の記号列へ置き換えるためのルールです。
応用情報（AP）
オートマトンと形式言語
BNF
BNFとは、プログラミング言語などの文法を一定のルールで記述するための代表的な記法です。