在Java中給出上下文無關語法驗證字符串

某人如何驗證字符串是否是上下文無關語法的一部分？不只是虛擬的，而是爲它建立一個算法？在Java中給出上下文無關語法驗證字符串

考慮到與規則，如

V-> V1V2
V1-> 1的上下文無關文法| 1v1
v2-> 2 | 2v2

很明顯，這是語言1^n 2^n。但是，你將如何處理算法來驗證它是否真的存在。我正在嘗試在java中完成此操作。

2013-03-23 Iordanis

你想驗證一個字符串是由CFG生成的，還是CFG的語言是你所說的？ – templatetypedef 2013-03-23 23:57:09

如果字符串是有效的，意味着它屬於上下文無關語言，其上下文無關語法被提供。 – Iordanis 2013-03-24 00:00:06

您可能想要查看Earley's algorithm或CYK algorithm，這兩個算法用於決定字符串是否由上下文無關語法生成。對於任何長度爲n的字符串，Earley的算法在時間O（n ）中運行，而不管語法中的生產規則如何（儘管大O符號中的常數項取決於語法），而CYK算法要求語法首先轉換爲Chomsky normal form以保證O（n ）運行時。

希望這會有所幫助！

來源

2013-03-24 00:03:57 templatetypedef

是的，它有很大的幫助。還有一個問題與你的答案有關。是否有可能實現epsilon轉換？ – Iordanis 2013-03-24 00:09:58

考慮到NFA與ε-moves和常規NFA是等價的，答案將是「是可能的」。資料來源：http：//en.wikipedia.org/wiki/Nondeterministic_finite_automaton_with_%CE%B5-moves – 2013-03-24 00:50:41

@ StephenC-NFA和DFA是正式語言的形式，而不是上下文無關的語言。 – templatetypedef 2013-03-24 01:56:17

在Java中給出上下文無關語法驗證字符串

回答

相關問題