オートマトンと言語理論

文脈自由文法と導出木、最左導出と最右導出の性質と例について

文脈自由文法とは文脈自由文法 (Context-Free Grammar, CFG) は、形式言語理論で使われる文法の一種です。基本的な要素ここで、この数式の意味は次のようになっています。 \( …
正規文法と定義・具体例・生成規則・例題・有限オートマトンについて

正規文法とは $ N $：非終端記号の集合。これは文法の生成規則で使われる記号の集合です。通常、大文字のアルファベット（例：$ A, B, C $）が使われます。 $ \Sigma $： …
文脈自由言語でない言語とポンピング補題・uvwxy定理・例題について

ポンピング補題 uvwxy定理や反復補題、繰り返しの定理とも呼ばれる。文脈自由言語（Context-Free Language, CFL）ではない言語を示す方法の一つとして、「ポンピング補題」がよく使 …
正規文法と定義・具体例・生成規則・例題・有限オートマトンについて

正規文法とは $ N $：非終端記号の集合。これは文法の生成規則で使われる記号の集合です。通常、大文字のアルファベット（例：$ A, B, C $）が使われます。 $ \Sigma $： …
文脈自由文法と導出木、最左導出と最右導出の性質と例について

文脈自由文法とは文脈自由文法 (Context-Free Grammar, CFG) は、形式言語理論で使われる文法の一種です。基本的な要素ここで、この数式の意味は次のようになっています。 \( …
オートマトンや形式文法でよく出る～記号・用語～

集合演算 A,Bを集合としたとき、以下の演算がよく用いられる。和集合和集合は、2つ以上の集合を合わせてできる集合のことで、記号は $\cup$ で表されます。例えば、集合 $A = \lbrace …
決定性有限オートマトン（DFA）と非決定性有限オートマトン（NFA）の意味と違いについて

オートマトンとはオートマトンとは、自動的に動作する機械やシステムの数学的なモデルであり、英語では”automaton”（単数）または”automata”（複数）と呼ばれます。決定性有限オートマトン …
【Python】簡単に状態遷移図を作成することができる！automata-libの使い方について

automata-lib 今回はpythonのライブラリであるautomata-libの使い方について説明させていただきます。これが使えれば、答えのないオートマトンの問題（大学の教科書）の助けになりま …