PR
オートマトンと言語理論
-
文脈自由言語でない言語とポンピング補題・uvwxy定理・例題について
ポンピング補題 uvwxy定理や反復補題、繰り返しの定理とも呼ばれる。文脈自由言語（Context-Free Language, CFL）ではない言語を示す方法の一つとして、「ポンピング補題」がよく使 …
-
正規文法と定義・具体例・生成規則・例題・有限オートマトンについて
正規文法とは \( N \)：非終端記号の集合。 これは文法の生成規則で使われる記号の集合です。通常、大文字のアルファベット（例：\( A, B, C \)）が使われます。 \( \Sigma \)： …
-
文脈依存文法の定義・具体例・生成規則・オートマトンについて
文脈依存文法とは ここで、文脈自由文法と同様に、各要素の意味は次の通りです。 \( N \) (非終端記号の集合): 文法で使用される非終端記号の集合。 \( \Sigma \) (終端記号の集合): …
-
文脈自由文法と導出木、 最左導出と最右導出の性質と例について
文脈自由文法とは 文脈自由文法 (Context-Free Grammar, CFG) は、形式言語理論で使われる文法の一種です。 基本的な要素 ここで、この数式の意味は次のようになっています。 \( …
-
決定性有限オートマトン（DFA）と非決定性有限オートマトン（NFA）の意味と違いについて
オートマトンとは オートマトンとは、自動的に動作する機械やシステムの数学的なモデルであり、英語では”automaton”（単数）または”automata”（複数）と呼ばれます。 決定性有限オートマトン …
-
【Python】簡単に状態遷移図を作成することができる！automata-libの使い方について
automata-lib 今回はpythonのライブラリであるautomata-libの使い方について説明させていただきます。これが使えれば、答えのないオートマトンの問題（大学の教科書）の助けになりま …