我真的很感谢你的帮助,这决定了字母表中所有单词的语言是否都是{0,1}无法从同一方面读取的,是一种无上下文的语言(也就是说,它可以转换成特定的语法)规则).{ w | w <> wR }
我试图通过泵浦引理证明它不是一种无上下文的语言,但是我找不到会导致我矛盾的字符串.
有什么建议？
我是CFG的新手,
有人可以给我一些关于创建生成某种语言的CFG的技巧
例如
L = {am bn | m >= n}
我得到的是:
So -> a | aSo | aS1 | e
S1 -> b | bS1 | e
但是我认为这个领域是错误的,因为有可能的数量b可能大于a.
grammar lexical-analysis context-free-grammar formal-languages
我已经看到这个算法应该可以用来删除所有左递归.然而,我遇到了这个特殊语法的问题:
A -> Cd
B -> Ce
C -> A | B | f
无论我尝试什么,我最终都在循环中或使用仍然间接留下递归的语法.
在这个语法上正确实现这个算法的步骤是什么？
假设我们有一个简单的语法规范.有一种方法可以枚举该语法的术语,通过对角迭代来保证任何有限项都具有有限的位置.例如,对于以下语法:
S ::= add
add ::= mul | add + mul
mul ::= term | mul * term
term ::= number | ( S )
number ::= digit | digit number
digit ::= 0 | 1 | ... | 9
您可以枚举这样的术语:
0
1
0+0
0*0
0+1
(0)
1+0
0*1
0+0*0
00
... etc
我的问题是:有没有办法做相反的事情？也就是说,采用该语法的有效术语,比如说0+0*0,并在这样的枚举中找到它的位置 - 在这种情况下,9？
我必须确定一种语言(例如L = {a ^ nb ^ mc ^ s | 0 <= n <= m <= s})是否是常规的,无上下文的,递归的,递归可枚举的或者都不是.
我知道如何确定一个语言是正规(找到DFA或正则表达式的工作)或上下文(找到一个PDA或上下文无关文法的作品); 我知道递归语言有一个总是停止的图灵机器,并且一个递归可枚举的语言有一个可能不会停止的图灵机.
所以问题是:是否有一个快速的标准来确定语言是递归还是递归可枚举或两者都没有？例如,我不需要构建一个PDA来理解语言是无上下文的,我不能通过它需要一个堆栈来看待它; 有没有类似的快速解决问题的方法(希望能省去构建图灵机的麻烦)？
recursion computer-science turing-machines context-free-grammar
我试图证明以下内容:
如果G是乔姆斯基范式中的无上下文语法,那么对于任何字符串w属于长度n≥1的L(G),它需要恰好2n-1步才能得出w的任何推导.
我该如何证明这一点？
我每天都会看到关于"如何用regexen做X"的帖子.而对他们中的大多数人的最佳反应似乎就是老实说,"你为什么要用锤子开螺丝？" 但regexen无处不在,语法大多是可移植的,特别是如果你远离花哨的位.
有没有相当于regexen但在功能和可配置性方面更上一层楼的东西？一个"你可以在任何地方使用它"解析各种各样的库,最好用一个光彩照人的简洁DSL作为它的界面？
我有点使用Ragel,但由于预处理步骤,我会毫不犹豫地推荐给某人"使用这个而不是一些毛茸茸的正则表达式".从Obj-C中使用它很尴尬,我认为从一个没有编译链接运行的语言来看它将是非常尴尬的,因为它是标准操作过程的一部分.
我正在寻找的东西将通过"内联在线通用"测试.
(内联)您可以使用其他代码内联编写符号,就像使用正则表达式一样.
(在线)您可以像运行其他代码一样运行生成的解析器,这意味着在Python之类的情况下输入到REPL之后.
(通用)您可以移动到不同的语言/平台,并为解析器使用几乎相同的代码,模数方差.实际上,我对使用Python,Ruby,C,Java和Haskell的东西感到满意.
我所知道的大多数工具都是"在线".他们离线预处理语法并用目标语言(C,Python,Java,C++ ......)吐出代码.它们是独立的工具,它们本身并没有集成到语言环境中.
我有PEG解析器和lex/yacc组合的建议.解析器组合库也可能是一个很好的选择.无论你提出什么建议,我都希望看到它能够满足这些测试要求.您的答案应该通过在Python,C和Haskell中提供可用的演示解析器来证明所提出的解决方案符合内联在线通用要求.演示示例由作者决定,但使用正则表达式应该是痛苦的,但使用适当的解析器则是微不足道的.
import nltk
from nltk.parse import ViterbiParser
def pcfg_chartparser(grammarfile):
f=open(grammarfile)
grammar=f.read()
f.close()
return nltk.PCFG.fromstring(grammar)
grammarp = pcfg_chartparser("wsjp.cfg")
VP = ViterbiParser(grammarp)
print VP
for w in sent:
for tree in VP.parse(nltk.word_tokenize(w)):
print tree
当我运行上面的代码时,它为句子产生以下输出,"关灯" -
(S(VP(VB转)(PRT(RP关))(NP(DT)(NNS灯))))(p = 2.53851e-14)
但是,它会引起句子的以下错误,"请关掉灯" -
ValueError:语法不包含一些输入词:u"'please'"
我正在通过提供概率上下文无关语法来构建ViterbiParser.它适用于解析具有已经在语法规则中的单词的句子.它无法解析Parser在语法规则中没有看到单词的句子.如何解决这个限制？
我指的是这个任务.
将下面的语法转换为乔姆斯基范式.给出所有中间步骤.
S -> AB | aB
A -> aab|lambda
B -> bbA
好的,我做的第一件事就是添加一个新的起始变量 S0
所以现在我有
S0 -> S
S -> AB | aB
A -> aab|lambda
B -> bbA
然后我删除了所有的lambda规则:
S0 -> S
S -> AB | aB | B
A -> aab
B -> bbA | bb
然后我检查S->S并A->B输入不存在的规则.这就是我提出的答案,我是否需要做更多的事情或者我做错了什么？