Reputation: 23
I am a computer science student on my second and year and we are given a nondeterministic finite automaton and asked what words does it accept.
I tried simplifying it to a deterministic finite automaton and ended up with this:
i councluded that is does not accept any word in the format of b* or a or a(b+ab*a)* , cant figure out what is common between them and what words it accepts,I figured this this much, it is not relevant to the whole word , only to the beginning because if the word start with aa it can have any combination of a and b and it wont matter it will be accepted.
would really appreciate the help.
Upvotes: 2
Views: 876
Reputation: 28292
First, I will answer the question in my own way. Then, I will address your conversion to a deterministic finite automaton.
We can write a set of equations and solve for q2 to see what regular expression leads to that state. Consider the following system:
(q1) = (q2)a + e
(q2) = (q1) + (q3)(a + b)
(q3) = (q1)a + (q3)b
We want to solve for what leads to the accepting state, so let's eliminate the non-accepting ones first:
(q1) = (q2)a + e
(q2) = (q2)a + e + (q3)(a + b)
(q3) = (q2)aa + a + (q3)b
To eliminate (q3) we can use the rule (x) = r + (x)s <=> (x) = rs* and then substitute:
(q1) = (q2)a + e
(q3) = ((q2)aa + e)b*
(q2) = (q2)a + e + ((q2)aa + a)b*(a + b)
= (q2)a + e + (q2)aab*(a + b) + ab*(a + b)
= (q2)[a + aab*(a + b)] + [e + ab*(a + b)]
= (e + ab*(a + b))(a + aab*(a + b))*
= (e + ab*(a + b))(a(e + ab*(a + b)))*
The regular expression we recover basically describes this:
Get to q2 either by taking the empty transition, or going through q3; then, get back to q2 by going to q1 and repeating the first part. You can do this as many times as you want.
How do you write the system?
To determinize a finite automaton, consider each subset of states and add transitions as you go. We start with the subset {q1} consisting of only the initial state.
/------------------------------------\
| __ |
V / \ |
{q1} -a-> {q1,q3} -a-> {q1,q2,q3} a |
| | | ^__/ |
b b b |
| __ | | |
V / V V | |
{ } b {q2,q3} <--------/ |
^ \__/ \ |
| \-a->{q1,q2}-----a----/
| |
\----------b----------/
The rules for adding states and transitions are:
Note: in the above automaton, I have not shown the transitions on the dead state { }. All transitions originating in a dead state terminate in a dead state.
My {q1} is analogous to your uppermost (OK). My { } is analogous to your HOLE. My {q1,q3} is analogous to your NOT. My {q2,q3} is analogous to your rightmost OK.
However - my {q1,q2,q3} is NOT analogous to your bottommost OK. To make yours like mine, add a transition from your bottommost OK to your rightmost OK on symbol b.
Note that my {q1,q2} is redundant and is equivalent to my {q1}; all transitions out of {q1,q2} are the same as those out of {q1}. Really, because of the e-transition from q1 to q2, I should have made {q1,q2} the initial state, but whatever - you get the idea.
The reason your DFA can't be right is that in the NFA, there's always a chance to "blow it" and end up in the hole. In your automaton, you can get to the bottommost OK and then be set.
Upvotes: 1