chomsky-hierarchy

4熱度

2回答

我想解析一種編程語言。我閱讀了很多關於正式語言和喬姆斯基層次結構和ANTLR的內容。但是，我無法找到有關如何將ANTLR v3作爲LL（*）遞歸下降解析器接受到的語言與層次結構關聯的信息。 Chomsky類型如何與LL（*）混合？任何信息（在線，書籍，論文）非常感謝。編輯：ANTLR的句法/語義謂詞和回溯如何映射到這裏？

0熱度

1回答

正規文法到我的正則表達式/ DFA

我有以下的正則表達式：（（ABC）+ d）|（？EF * G）我創建了一個DFA（我希望這是正確的），你可以看到這裏 http://www.informatikerboard.de/board/attachment.php?attachmentid=495&sid=f4a1d32722d755bdacf04614424330d2 的任務是創建一個常規的語法（喬姆斯基層次類型3），我不明白這一點。

0熱度

1回答

上下文敏感語法

我找描述以下語言的上下文敏感語法： L = { ww | w ∈ {a,b}*, |w| ≥ 1} <br> 我有這樣一個事實的問題，沒有規則，如X - >ε是允許的，因此我不能放置任何表示單詞「中間」的非終結符。這個問題有什麼竅門嗎？如果你碰巧知道答案，請幫忙。

0熱度

1回答

有限和無限語言混淆

我最近開始學習形式語言理論，並遇到了有限和無限語言的一些問題。我被告知所有有限的語言都是常規的。然而，通讀給我的，語法與製作筆記： S --> ab S --> aabb S --> aaabbb 不是正規的語言雖然製作生成的字符串的數量有限。然而，隨着製作一個語法： S --> Sb S --> Tb T --> Ta T --> a 哪個生成形式的^ M B^

1熱度

1回答

將語言規範轉換爲生產規則（不知道它是CFG還是CSG）

我必須編寫一個函數來檢查輸入字符串是否對給定語言規範有效。我認爲這將是一個標準的CFG - >喬姆斯基規範形式，然後是CYK解析，但是語言中的規則之一是防止這種情況發生。一些規則是簡單的，如果我們定義端子{a,b,c,d,e,f,P,Q,R,S}，然後有效字符串是 1）任何在隔離小寫端子 2）如果「X」是一個有效的字符串，則所以是SX 但第三個原則是 3）如果X和Y是有效的輸入字符串，那麼這樣的

4熱度

4回答

遞歸語言與上下文敏感語言

在喬姆斯基的層次結構中，沒有定義遞歸語言的集合。我知道遞歸語言是遞歸可枚舉語言的子集，所有遞歸語言都是可確定的。我很好奇的是遞歸語言與上下文敏感語言的比較。我能否假設上下文敏感語言是遞歸語言的嚴格子集，因此所有上下文敏感語言都是可判定的？

-1熱度

2回答

什麼樣的語言是SQL？

SQL是一種上下文無關語言還是其他類型的語言？

1熱度

1回答

正則表達式解析類型-3語法

閱讀Chomsky hierarchy ... ...我知道正則表達式無法解析類型2語法（上下文無關文法），也是類型1和類型0。正則表達式可以解析/捕獲所有類型3語法（regular grammars）嗎？