questions on nfa and dfa..

Question

Hi Guys... 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.a*ba*ba*

3.a*ba*b(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....

Answer 1

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.

Answer 2

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.

Answer 3

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 also have 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?