In other word,if u give an input string x ,following this model will tell u if the string x works or not.
Example:Devise a DFSA that accepts the language of fi nite binary strings with odd numbers of 1's.
What we do in the normal life is just counting how many 1's are there in the binary string. But for a function or a program, the machine will have to go through all the number from the first till the end.
We have to count how many states are there for this model first.
As for this example, they are only 2 states:
a)odd number of 1's (accepting state)
b)even number of 1's
Think as a machine,we may start from the first number in the string.
But, we have to consider the starting state that even the first number has not been considered.
Appearently ,an empty binary string has even number of 1's (0 1's).
Then we know that if the next number is 1 the total number of 1's will change to another state. However 0 doesnt change the state.
The diagram will be :
And q1 the accepting state.
From the graph we know that a number 0 doesnt change the situation of whether the string has even or odd number of 1's.
So we can simplify it to
Now we are done!

没有评论:
发表评论