Questions about nfa and dfa
Hope you can help me with this ...
My main question is, "How do I determine if a regex will be accepted by NFA and / or DFA ?"
For example, my question says which regex is equivalent? explain ... 1. (a + b) ** b (a + b) ** b (a + b) *
2.ababa *
3.abab (a + b) *
Do we need to draw NFA and DFA and then find a minimization algorithm? if so how do we know which regex is accepted by the NFA / DFA so we can start with the answer? it's so confusing ....
The second is very similar, the question requires me to show that the language (a ^ nb ^ n | n> 1} is not accepted by the DFA ... grrrrr ... how do I know that? (BTW is a collection of all lines, where a the same number follows b) ....
I hope I explained well ....
a source to share
First, a note on terminology: a language is a collection of strings over some alphabet. DFA and NFA recognize regular languages, not regular expressions. There can be multiple regular expressions that define the same language. For two languages L1 and L2, if each member of L1 is a member of L2, and vice versa, than L1 and L2 are equivalent.
Regarding your first question, the L1 language consists of all lines over {a, b} with at least two "b" s. The L2 language consists of all lines above {a, b} with exactly two "b" s. The string "abbb" is part of L1 and L3, but not L2. Thus, the leaves of L1 and L3 are compared. Any element S from L1 must contain at least two letters. Let the first two "b" in S correspond to two explicit "b" in the expression E3; then the rest of the 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 from L3 must contain at least two "b" s. Let them match two explicit "b" s in the expression E1; other components (a+b)*
, (a+b)*
and(a+b)*
will also have matches, and S is also in L1. 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 pumpdown lemma . Suppose you have a DFA that has adopted that language ... show that it must also accept strings in a non-language, so such a DFA cannot exist. Let S be any string in the language ... any substring of S will either have all a, all b, or both ... so what happens after you "pump" it?
a source to share
NFA and DFA 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 the language is missing from the class, you usually use the pumping lemma.
Wikipedia has a very similar example, except for n> = 0; However, I will not complete your homework for you.
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.
a source to share
If you are asked to show that a language not accepted by DFA / NFA, you almost always have to apply Lemma pump , which is used for this purpose .
a source to share