希望你能帮我解决这个问题......
我有一个主要问题是''如何判断正则表达式是否会被NFA和/或DFA接受？
例如。我的问题是哪个正则表达式是等价的？解释... 1.(a+b)**b(a+b)**b(a+b)*
2.呸呸呸*
3.a ba b(a+b)*
我们是否必须绘制NFA和DFA然后通过最小化算法找到？如果我们这样做，那么我们如何知道 NFA/DFA 接受哪个正则表达式，以便我们可以从答案开始？它是如此混乱....
第二个是一个非常相似的问题，问题要求我表明语言 (a^nb^n|n>1} 不被 DFA 接受...grrrrr...我怎么知道这个？（顺便说一句，这是一个所有字符串的集合，其中多个 a 后跟相同数量的 b)....
我希望我解释清楚......
首先，关于术语的说明：一种语言是一些字母表上的一组字符串。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一定是等价的。
关于你的第二个问题：使用抽水引理。假设您有一个接受该语言的 DFA……表明它也必须接受不是该语言的字符串，因此不存在这样的 DFA。让 S 是语言中的任何字符串... S 的任何子字符串要么全部为 a，要么全部为 b，或两者兼有……那么在“泵送”它之后会发生什么？
NFA 和 DFA 接受等效（常规）语言，因此显示一种语言是常规的一种方法是为其创建 NFA 或 DFA。
为了表明一种语言不在一个类中，您通常会使用抽水引理。
维基百科有一个非常相似的例子，除了 n>=0; 不过，我不会为你完成你的作业。
http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages
要确定两个正则表达式是否不等价，请创建一个被其中一个接受但被另一个拒绝的字符串。