問題タブ [context-free-language]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
context-free-grammar - CFG の構築
私は文字通りこれに対する答えを見つけることができません：
L = {vw | {a,b) の v 要素、{b,c} の w 要素、aの数 <= c の数}
V --> aV | bV | e
W --> bW | CW | e
しかし、単語 v と w の構成を次々に組み合わせて、前述の制限を念頭に置いて、どのように組み合わせるかを考えることはできません。
parsing - 決定論的文脈自由文法対文脈自由文法?
比較言語のクラスのノートを読んでいるのですが、少し混乱しています...
文脈自由文法と決定論的文脈自由文法の違いは何ですか? 私は特に、CFG のパーサーが O(n^3) であり、DCFG のコンパイラが O(n) である方法について読んでいますが、時間の複雑さの違いがどのように大きくなるかを本当に理解していません (言うまでもなく、 CFGをDCFGにする特性についてはまだ混乱しています）。
よろしくお願いします！
grammar - この言語の文法を見つける
次の言語の文脈自由文法を見つける必要があります。
L= { w from { a,b,c,d }* : #a+2#b=2#c+#d }
これが私の試みですが、それが正しいとは思えません：
automata - n と m の間に何らかの関係があるような言語 a^nb^m を考えると、与えられた言語は規則的ではないことを意味します。正しいですか?
私は、正規言語と文脈自由言語とは何か、正規言語がどのように有限のメモリを必要とするか、およびその他の関連事項を知っています。私が懸念しているのは、a n b m がそのようなものでnありm、それらの間に何らかの関係がある場合、それらは規則的ではあり得ないと思いますが、そのようなことはどこにも書かれていません。私はそう述べるのが正しいですか？