希望你帮我这个....问题和DFA
我这是“”如何判断一个正则表达式将NFA和/或DFA接受的主要问题？
例如，我的问题是说哪个正则表达式是等价的？解释... 1.（A + B）** B（A + B）** B（A + B）*
2.A BA BA *
3.A BA b（a + b）*
我们是否必须绘制NFA和DFA，然后通过最小化算法找到？如果我们这样做，那么我们如何才能知道NFA/DFA接受哪个正则表达式，以便我们可以从答案开始？它很混乱......
其次是一个非常相似的问题，该问题让我表明语言（a^nb^n | n> 1}不被DFA接受... grrrrr ...我怎么知道呢？（顺便说一句，这是一组，其中后跟相同数量的b的的数量的的所有字符串的）....
我希望我解释清楚以及....
如果你被要求表明，一些语言不是由DFA/NFA接受你几乎总是有应用pumping lemma，这是used exactly for that purpose。
的NFA和DFA的接受当量（REG ular）语言，因此表明语言经常使用的一种方法是为其创建NFA或DFA。
为了表明语言不在课堂上，您通常会使用抽象引理。
除非n> = 0，否则Wikipedia有一个非常相似的例子;不过，我不会为你完成作业。
http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages
要确定两个正则表达式是不等价的，创建一个由一个公认的，而是由其他拒绝的字符串。
首先，关于术语的说明：语言是一组字母上的字符串。 DFA和NFA识别常规语言，而不是常规表达式。可能有几个正则表达式定义相同的语言。对于两种语言L1和L2，如果L1中的每个成员都是L2的成员，反之亦然，则L1和L2是等价的。
关于你的第一个问题，语言L1由{a，b}上的所有字符串组成，至少至少两个'b'。语言L2由{a，b}上的所有字符串组成，其中正好为两个'b'。 字符串“abbb”是L1和L3的元素，但不是L2。因此，L1和L3 进行比较。任何L1的元素S必须包含至少两个'b'。让S中的前两个'b的 与表达式E3中的两个显式'b'匹配;那么其他组件a*,a*和(a+b)*总是可以匹配的，并且S必须在L3中。因此L1是L3的一个子集。类似地，L3的任何元素S必须包含至少两个“b”。让那些符合表达式E1中两个明确的'b';其他组件(a+b)*,(a+b)*,(a+b)*也将 有匹配，并且S也在L1中。所以L1是L3的一个子集，L3是L1的一个子集，所以L1和L3必须是等价的。
关于你的第二个问题：使用pumping lemma。假设您有一个接受该语言的DFA ...表明它也必须接受不在该语言中的字符串，因此不能存在此类DFA。假设S是语言中的任何字符串...... S的任何子字符串都可以包含所有的a，b，或者两者都有......那么在你“泵”它之后会发生什么？
感谢Jim .....太多了....我试过了，但是可以在第二个上再投光一些.....再次感谢...... – Lopa 2010-04-24 03:41:57
@Loop：假设DFA有n个状态，但接受任意长的字符串的语言。那么DFA必须有一个循环，并且该循环具有n个或更少的状态转换。因此，任何输入字符串都会在该循环中使用DFA，并且可以“抽取”（重复）任意次数的子字符串，并且仍然可以被DFA接受。 – 2010-04-24 03:49:27
嗨......是不是有任何简单或简短的方式表明DFA/NFA的接受度？ – Lopa 2010-04-24 02:49:36
@Loop：显示一种语言被接受，并表明它不能被接受是两种不同的问题。这个'a^nb^n'问题的意图当然是你使用抽象引理。 – sth 2010-04-24 02:59:16