关于nfa和dfa的问题
希望你能帮助我解决这个问题......
我有一个主要问题是“如何判断正则表达式是否会被 NFA 和/或 DFA？
例如。我的问题是哪些正则表达式是等效的？解释... 1.(a+b)**b(a+b)**b(a+b)*
2.ababa*
3.abab( a+b)*
是否必须先画出NFA和DFA，然后通过最小化算法求？如果我们这样做，那么我们如何知道 NFA/DFA 接受哪个正则表达式，以便我们可以从答案开始？太令人困惑了....
第二个是一个非常相似的问题，问题要求我表明该语言 (a^nb^n|n>1} 不被 DFA 接受...grrrrr...我怎么知道这个？（顺便说一句，这是一组所有字符串，其中多个 a 后面跟着相同数量的 b）....
我希望我解释得清楚......
Hope you help me with this one....
I have a main question which is ''how to judge whether a regular expression will be accepted by NFA and/or DFA?
For eg. My question says that which of the regular expressions are equivalent? explain...
1.(a+b)**b(a+b)**b(a+b)*
2.ababa*
3.abab(a+b)*
do we have to draw the NFA and DFA and then find through minimisation algorithm? if we do then how do we come to know that which regular expression is accepted by NFA/DFA so that we can begin with the answer? its so confusing....
Second is a very similar one, the question asks me to show that the language (a^nb^n|n>1} is not accepted by DFA...grrrrr...how do i know this? (BTW this is a set of all strings of where a number of a's is followed by the same number of b's)....
I hope I explained clearly well....
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
首先，关于术语的说明：语言是某些字母表上的一组字符串。 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”。让前两个 'b'
S 中匹配表达式 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，或两者都有...那么在“泵送”它之后会发生什么？
First, a note about terminology: A language is a set of strings over some alphabet. DFAs and NFAs recognize regular languages, not regular expressions. There may be several regular expressions that define the same language. For two languages L1 and L2, if every member of L1 is a member of L2, and vice versa, than L1 and L2 are equivalent.
Regarding your first question, the language L1 consists of all strings over {a,b} with at least two 'b's. Language L2 consist of all strings over {a,b} with exactly two 'b's.
The string "abbb" is an element of L1 and L3, but not L2. So that leaves L1 and L3
to compare. Any element S of L1 must contain at least two 'b's. Let the first two 'b's
in S match the two explicit 'b's in expression E3; then the other components
a*,a*, and(a+b)*can always be matched, and S must be in L3. Therefore L1 is a subset of L3.Similarly, any element S of L3 must contain at least two 'b's. Let those match the two explicit 'b's in expression E1; the other components
(a+b)*,(a+b)*, and(a+b)*will alsohave matches, and S is in L1 too. So L1 is a subset of L3, and L3 is a subset of L1, so
L1 and L3 must be equivalent.
Regarding your second question: use the pumping lemma. Suppose you had a DFA that accepted that language...show that it also must accept strings not in the language, therefore no such DFA can exist. Let S be any string in the language...any substring of S will either have all a's, all b's, or both...so what happens after you "pump" it?
NFA 和 DFA 接受等效（常规）语言，因此表明某种语言是常规语言的一种方法是为其创建 NFA 或 DFA。
为了表明某种语言不属于某个类，您通常会使用泵引理。
维基百科有一个非常相似的例子，除了n>=0；不过，我不会替你完成作业。
是否
确定两个正则表达式 不等价，创建一个被一个接受但被另一个拒绝的字符串。
NFAs and DFAs accept equivalent (regular) languages, so one way to show that a language is regular is to create an NFA or DFA for it.
To show that a language is not in a class, you typically would use the pumping lemma.
Wikipedia has a very similar example, except n>=0; I won't finish your homework for you, though.
http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages
To determine if two regular expressions are not equivalent, create a string that is accepted by one, but rejected by the other.
如果您被要求证明 DFA/NFA 不接受某种语言，您几乎总是必须应用 泵引理，正是用于此目的。
If you are asked to show that some language is not accepted by a DFA/NFA you almost always have to apply the pumping lemma, which is used exactly for that purpose.