Can anybody explain a finite automaton?
I have to program one for class and I've read the instructions for hours! I still haven't the slightest idea of what's going on!
So only post if you know what one is please.
Finite Automaton
Finite Automaton
Conrad R.
-
MegaFighter_X
- Post Master General
- Posts: 2334
- Joined: 27 Apr 2003 16:52
- Location: Las Vegas
- Contact:
This assignment involves a simple device called a finite automaton (abbreviated FA). An FA has a set of states, which we will assume are numbered from 0 through n (where n is some nonnegative integer). One state, which we will always take to be state 0, is designated as the initial state. Certain states (one or more) are designated as accepting states. The way the device works is that it receives a sequence of inputs, which for the purpose of this assignment we will assume are either 0 or 1. The device has a transition function f, which can be described as follows. At any time, we think of the device as being in some state, say q. If when it is in the state q it receives the input i, the new state that it will be in as a result is f(q,i). In other words, f is a function of two variables, where the first variable represents a state and the second represents an input, and the value of the function is a state.
The FA starts in the initial state 0 and receives a sequence of inputs, say i0, i1, i2, ..., ik. (Each one is one of the integers 0 or 1.) After each input, it is in a certain state. (After the input i0, it is in state q1 = f(0, i0). After the input i1, it is in state q2 = f(q1, i1). ... After the input ik, it is in state f(qk, ik).) We say the sequence of inputs is accepted if the state the FA is in after receiving the entire sequence is one of the accepting states.
Here's a simple example. Suppose there are three states, 0, 1, and 2, and that the only accepting state is 2. Suppose the transition function f is given by the table below:
q f(q,0) f(q,1)
0 0 1
1 2 1
2 0 1
Then you can check that for the sequence of inputs 0110101, the FA starts in state 0 and goes to state 0, state 1, state 1, state 2, state 1, state 2, and finally state 1. Therefore, this sequence of inputs is not accepted. The sequence 10010 causes the FA to go (starting from the initial state 0) to state 1, state 2, state 0, state 1, and finally state 2. Therefore, this sequence is accepted. In fact, it's not hard to see that for this example, the sequences of inputs that are accepted are precisely the sequences of two or more inputs, in which the last two inputs are 10.
Here's another example. This time there are 6 states, 0, 1, 2, 3, 4, and 5. Again the only input symbols are 0 and 1, but this time there are two accepting states, 4 and 5. The transition function is described below.
q f(q,0) f(q,1)
0 1 2
1 0 3
2 5 3
3 4 2
4 1 3
5 0 3
It's not hard to see that this FA accepts precisely the same sequences as the first one. This means that it's more complicated than it needs to be: in order to accept the sequences that end in 10, we don't need 6 states---3 is sufficient.
The problem in this assignment is to start with an FA and to decide whether it is as simple as possible (i.e., has as few states as possible), or whether there is another FA with fewer states that accepts exactly the same input sequences. In the second case, we would like to find the simplest possible such FA. We can summarize the problem by saying that we are trying to minimize a given FA---i.e., to find the one with the fewest possible states that accepts exactly the same sequences of inputs. Let us now describe the method we can use to solve this problem. We consider two arbitrary states, say p and q, and we ask whether they are really both necessary, or whether they might be combined into a single state. It seems clear that they cannot be combined if there is some sequence of inputs which would cause the FA to go from state p to an accepting state and from state q to a nonaccepting state (or vice versa). In other words, they cannot be combined if for some sequence of inputs, the answer the FA gives for that sequence (yes or no) if it starts in state p will be different from the answer it gives for that sequence if it starts in state q.
One way of thinking about the solution is to consider every possible pair (p,q) of distinct states, and to try to use this criterion to decide whether p and q could be combined with each other. (To make it easier to describe the algorithm, let's introduce a set nonCombinable of pairs: a pair (p,q) will be added to nonCombinable if we find that the two states in the pair cannot be combined. So we can think of the problem as being to find all the noncombinable pairs and put them in the set.) The potential problem is that we might have to consider longer and longer sequences of inputs in order to decide this. So let's think about working backwards. Suppose we already know that some pair (r,s) is in nonCombinable. Suppose that there are two states p and q, and a single input i (either 0 or 1), so that f(p,i) = r, and f(q,i) = s (where f is the transition function). Then p and q can also not be combined, because if we have a sequence of inputs that produces different answers starting at r and starting at s, the longer sequence that consists of i followed by the original sequence will produce different answers starting at p and starting at q. We can summarize this by saying it this way: if the pair (r,s) belongs to nonCombinable, and if f(p,i) = r and f(q,i) = s (for some pair (p,q) and some input i), then the pair (p,q) should be added to nonCombinable.
The way we start this process is to initialize nonCombinable so that it contains the pairs (r,s) that can obviously not be combined, because one of them is an accepting state and the other isn't. (This is the same as thinking about the answers produced, starting at both r and s, after receiving the trivial "sequence" of no inputs at all. These answers are already different.) Once we have these pairs in the set, then we can start working backward as in the preceding paragraph. We make a sequence of passes. On each pass, we consider all pairs (p,q) that are not yet in nonCombinable, and we consider both possible inputs. If there is some input i so that the pair (f(p,i),f(q,i)) is in nonCombinable (i.e., f(p,i) = r and f(q,i) = s, where (r,s) is in nonCombinable), then we add the pair (p,q) to nonCombinable.
What makes this approach feasible is that if there is a pair (p,q) that should be in nonCombinable, because some sequence of k inputs would produce different answers starting at p and q, then this pair will certainly have been put into the set by the end of the kth pass. Furthermore, the algorithm is guaranteed to terminate, because after any pass in which no new pairs have been added, we can stop (since no additional passes would cause any new pairs to be added).
Let's trace the algorithm for the second FA described above. The pairs of distinct states are:
(1,0)
(2,0), (2,1)
(3,0), (3,1), (3,2)
(4,0), (4,1), (4,2), (4,3)
(5,0), (5,1), (5,2), (5,3), (5,4)
(Note: order is irrelevant. So we don't need to list both (1,0) and (0,1), for example.)
Since the accepting states are 4 and 5, we start by placing in nonCombinable all pairs containing either 4 or 5 but not both. We will show the pairs currently in the set by underlining it.
(1,0)
(2,0), (2,1)
(3,0), (3,1), (3,2)
(4,0), (4,1), (4,2), (4,3)
(5,0), (5,1), (5,2), (5,3), (5,4)
On the first pass, we consider the pairs not in the set. The status of (1,0) doesn't change, because the input 0 takes (1,0) to (1,0) and the input 1 takes it to (3,2), and neither of these is in the set. The pair (2,0) is added, however, since the input 0 takes (2,0) to (5,1), which is in the set. Similarly, (2,1) is added, since input 0 takes it to (5,0). The pairs (3,0) and (3,1) are added for similar reasons. The pair (3,2) doesn't change, since neither input takes it to a pair in the set. Finally, the pair (5,4) doesn't change either. So at the end of the first pass, we have
(1,0)
(2,0), (2,1)
(3,0), (3,1), (3,2)
(4,0), (4,1), (4,2), (4,3)
(5,0), (5,1), (5,2), (5,3), (5,4)
Since there were pairs added to the set on the first pass, we must perform another pass. However, it's easy to see that none of the 3 remaining pairs gets added on this pass, and so we're done after two passes. Since (1,0) is not in the set, we conclude that 0 and 1 could be combined. Since (3,2) is not in the set, 2 and 3 could be combined. And since (5,4) is not in the set, 4 and 5 could be combined. We conclude that only 3 states are necessary, and we could describe the 3 states as:
0 or 1
2 or 3
4 or 5
In this example, it turned out that every state could be combined with exactly one other state. Of course this doesn't always happen. For example, if we start with 6 states, and if after the algorithm terminates we end up with
(1,0)
(2,0), (2,1)
(3,0), (3,1), (3,2)
(4,0), (4,1), (4,2), (4,3)
(5,0), (5,1), (5,2), (5,3), (5,4)
(i.e., nonCombinable contains all the underlined pairs), then again we conclude that we only need 3 states, but this time the states can be described as
0 or 1 or 3
2 or 4
5
Another possibility, of course, is that after we have executed the algorithm, all possible pairs have been added to nonCombinable. In this case, we conclude that no states can be combined, and the original FA is already as simple as possible.
Your program should accept as input a string describing an FA (details below) and produce as output as many lines as there are states in the minimized FA, each line containing the states of the original FA that were combined into one.
The way a string will describe an FA is as follows: it will contain a number of ints, separated by one or more spaces. The first number is the total number n of states in the FA (which are to be thought of as numbered from 0 to n-1). After that are the 2*n numbers f(0,0), f(0,1), f(1,0), f(1,1), f(2,0), f(2.1), ..., f(n-1,0), f(n-1,1) (where f is the transition function, as explained above). Finally the last numbers in the string are the numbers of the accepting states. There may conceivably be none (in which case the FA obviously does not accept any sequences of inputs), and there may conceivably be as many as n (in which case the FA accepts every sequence of inputs); more likely, there will be at least one but fewer than n.
For example: in the case of the FA described above with six states, the input string would look like
6 1 2 0 3 5 3 4 2 1 3 0 3 4 5
and the output should look like
0 1
2 3
4 5
Suggestions. Use a class Pair (sort of like Point) having two int variables, a constructor with two int parameters, and two accessor methods getFirst() and getSecond(), which return the first and second numbers in the pair, respectively. (As we have seen above, (1,0) and (0,1) are really the same pair. For this reason, it would be appropriate for the constructor to interchange the two numbers if necessary so that the larger comes first.) Use two classes IntSet and PairSet representing sets of ints (in this application, sets of states) and sets of pairs. In each case it is sufficient to use a default constructor that initializes the set to have no elements. Appropriate methods in both classes include the following. (I've shown the parameters as ints, but in the case of PairSet they would be Pairs.)
add(int i) // add the element i to the set (if it's already there, do nothing)
delete(int i) // delete the element i from the set (if it isn't in the set, do nothing)
isElement(int i) // returns true if i is an element of the set, false otherwise
firstElement() // returns the first element of the set, or -1 if the set is empty
// (in the case of Pair, an appropriate return value if the set is empty is null)
nextElement(int i) // returns the element of the set that comes after i (if there is one), -1 otherwise
numElements() // returns the number of elements of the set.
print() // prints the elements of the set (useful for debugging purposes)
(Note: the firstElement and nextElement methods should be thought of as analogous to StringTokenizer; they simply provide a way of processing all the elements of a set, one at a time. The specific order in which the elements are processed doesn't really matter---the only important thing is that when used appropriately the methods allow you to do something with each element of the set.)
A good way to represent a set of ints in this program is to use a boolean array with n elements, where n is the number of states in the FA. So the elements of the array go from 0 through n-1. The ith element will be true if the integer i is in the set, false otherwise. So, for example, the way to do add(i) is simply to make the ith element true, provided of course that i is within the appropriate range. To do delete(i), make the ith element false.
A good way to represent a set of Pairs is to use a 2-dimensional boolean array with n rows and n columns, where n is the number of states. (Actually, this is somewhat wasteful, since the only positions in the array that we ever need to use are positions [j] where i>j, but all it means is that we're allocating approximately twice as much space as we need, so it's not terrible.). Note: the fact that we use only the positions [j] for which i>j is the reason for making sure that the Pair constructor always puts the larger number first. If it didn't do this, we could easily make mistakes---for example, add a Pair (i,j) to a set and later conclude by looking at the [j] position of the array that the pair is not in the set.
A good way to represent the transition function of the FA is to use an array f of type int[n][2] , where for example f[0] is the number written f(i,0) above.
Use a class Fa. Instance variables include an int numStates, an IntSet accepting, and an int array for the transition function. The constructor takes a string parameter. You can decide what methods are appropriate in order to do the minimization. Include a method minimize(), but do not allow it to get too big---have it call smaller helper methods. When I did it, I found it helpful to use three sets of Pairs: allPairs (containing all the pairs (i,j) for which 0<=j < i < numStates), combinable, and nonCombinable. In the initial phase of the minimization, we go through all the pairs and for each one, add it to nonCombinable if one of the numbers is an accepting state and the other isn't, and otherwise add it to combinable. Then we make a sequence of passes. In each pass, we go through every pair in combinable, and for each one, say (i,j), test it as above using the transition function, to see whether it should be deleted from combinable and added to nonCombinable. This continues until we do a pass in which no pairs are moved. When we've finished the passes, we then just have to figure out how to use the set nonCombinable (or the set combinable) in order to produce the appropriate output.
The class Pair should be more or less a triviality. I suggest that you then write the class IntSet and test it, then write the class PairSet and test it, and finally, write the Fa class along with a class FaTest containing the main method.
Your main program should allow a user to input a file name, and it should then read a sequence of strings from that file, each string representing another data item (i.e., another FA). You can add this feature at the very end; in the development of the program, you can just use a main program with two lines, such as
Fa m = new Fa("6 1 2 0 3 5 3 4 2 1 3 0 3 4 5");
m.minimize();
The FA starts in the initial state 0 and receives a sequence of inputs, say i0, i1, i2, ..., ik. (Each one is one of the integers 0 or 1.) After each input, it is in a certain state. (After the input i0, it is in state q1 = f(0, i0). After the input i1, it is in state q2 = f(q1, i1). ... After the input ik, it is in state f(qk, ik).) We say the sequence of inputs is accepted if the state the FA is in after receiving the entire sequence is one of the accepting states.
Here's a simple example. Suppose there are three states, 0, 1, and 2, and that the only accepting state is 2. Suppose the transition function f is given by the table below:
q f(q,0) f(q,1)
0 0 1
1 2 1
2 0 1
Then you can check that for the sequence of inputs 0110101, the FA starts in state 0 and goes to state 0, state 1, state 1, state 2, state 1, state 2, and finally state 1. Therefore, this sequence of inputs is not accepted. The sequence 10010 causes the FA to go (starting from the initial state 0) to state 1, state 2, state 0, state 1, and finally state 2. Therefore, this sequence is accepted. In fact, it's not hard to see that for this example, the sequences of inputs that are accepted are precisely the sequences of two or more inputs, in which the last two inputs are 10.
Here's another example. This time there are 6 states, 0, 1, 2, 3, 4, and 5. Again the only input symbols are 0 and 1, but this time there are two accepting states, 4 and 5. The transition function is described below.
q f(q,0) f(q,1)
0 1 2
1 0 3
2 5 3
3 4 2
4 1 3
5 0 3
It's not hard to see that this FA accepts precisely the same sequences as the first one. This means that it's more complicated than it needs to be: in order to accept the sequences that end in 10, we don't need 6 states---3 is sufficient.
The problem in this assignment is to start with an FA and to decide whether it is as simple as possible (i.e., has as few states as possible), or whether there is another FA with fewer states that accepts exactly the same input sequences. In the second case, we would like to find the simplest possible such FA. We can summarize the problem by saying that we are trying to minimize a given FA---i.e., to find the one with the fewest possible states that accepts exactly the same sequences of inputs. Let us now describe the method we can use to solve this problem. We consider two arbitrary states, say p and q, and we ask whether they are really both necessary, or whether they might be combined into a single state. It seems clear that they cannot be combined if there is some sequence of inputs which would cause the FA to go from state p to an accepting state and from state q to a nonaccepting state (or vice versa). In other words, they cannot be combined if for some sequence of inputs, the answer the FA gives for that sequence (yes or no) if it starts in state p will be different from the answer it gives for that sequence if it starts in state q.
One way of thinking about the solution is to consider every possible pair (p,q) of distinct states, and to try to use this criterion to decide whether p and q could be combined with each other. (To make it easier to describe the algorithm, let's introduce a set nonCombinable of pairs: a pair (p,q) will be added to nonCombinable if we find that the two states in the pair cannot be combined. So we can think of the problem as being to find all the noncombinable pairs and put them in the set.) The potential problem is that we might have to consider longer and longer sequences of inputs in order to decide this. So let's think about working backwards. Suppose we already know that some pair (r,s) is in nonCombinable. Suppose that there are two states p and q, and a single input i (either 0 or 1), so that f(p,i) = r, and f(q,i) = s (where f is the transition function). Then p and q can also not be combined, because if we have a sequence of inputs that produces different answers starting at r and starting at s, the longer sequence that consists of i followed by the original sequence will produce different answers starting at p and starting at q. We can summarize this by saying it this way: if the pair (r,s) belongs to nonCombinable, and if f(p,i) = r and f(q,i) = s (for some pair (p,q) and some input i), then the pair (p,q) should be added to nonCombinable.
The way we start this process is to initialize nonCombinable so that it contains the pairs (r,s) that can obviously not be combined, because one of them is an accepting state and the other isn't. (This is the same as thinking about the answers produced, starting at both r and s, after receiving the trivial "sequence" of no inputs at all. These answers are already different.) Once we have these pairs in the set, then we can start working backward as in the preceding paragraph. We make a sequence of passes. On each pass, we consider all pairs (p,q) that are not yet in nonCombinable, and we consider both possible inputs. If there is some input i so that the pair (f(p,i),f(q,i)) is in nonCombinable (i.e., f(p,i) = r and f(q,i) = s, where (r,s) is in nonCombinable), then we add the pair (p,q) to nonCombinable.
What makes this approach feasible is that if there is a pair (p,q) that should be in nonCombinable, because some sequence of k inputs would produce different answers starting at p and q, then this pair will certainly have been put into the set by the end of the kth pass. Furthermore, the algorithm is guaranteed to terminate, because after any pass in which no new pairs have been added, we can stop (since no additional passes would cause any new pairs to be added).
Let's trace the algorithm for the second FA described above. The pairs of distinct states are:
(1,0)
(2,0), (2,1)
(3,0), (3,1), (3,2)
(4,0), (4,1), (4,2), (4,3)
(5,0), (5,1), (5,2), (5,3), (5,4)
(Note: order is irrelevant. So we don't need to list both (1,0) and (0,1), for example.)
Since the accepting states are 4 and 5, we start by placing in nonCombinable all pairs containing either 4 or 5 but not both. We will show the pairs currently in the set by underlining it.
(1,0)
(2,0), (2,1)
(3,0), (3,1), (3,2)
(4,0), (4,1), (4,2), (4,3)
(5,0), (5,1), (5,2), (5,3), (5,4)
On the first pass, we consider the pairs not in the set. The status of (1,0) doesn't change, because the input 0 takes (1,0) to (1,0) and the input 1 takes it to (3,2), and neither of these is in the set. The pair (2,0) is added, however, since the input 0 takes (2,0) to (5,1), which is in the set. Similarly, (2,1) is added, since input 0 takes it to (5,0). The pairs (3,0) and (3,1) are added for similar reasons. The pair (3,2) doesn't change, since neither input takes it to a pair in the set. Finally, the pair (5,4) doesn't change either. So at the end of the first pass, we have
(1,0)
(2,0), (2,1)
(3,0), (3,1), (3,2)
(4,0), (4,1), (4,2), (4,3)
(5,0), (5,1), (5,2), (5,3), (5,4)
Since there were pairs added to the set on the first pass, we must perform another pass. However, it's easy to see that none of the 3 remaining pairs gets added on this pass, and so we're done after two passes. Since (1,0) is not in the set, we conclude that 0 and 1 could be combined. Since (3,2) is not in the set, 2 and 3 could be combined. And since (5,4) is not in the set, 4 and 5 could be combined. We conclude that only 3 states are necessary, and we could describe the 3 states as:
0 or 1
2 or 3
4 or 5
In this example, it turned out that every state could be combined with exactly one other state. Of course this doesn't always happen. For example, if we start with 6 states, and if after the algorithm terminates we end up with
(1,0)
(2,0), (2,1)
(3,0), (3,1), (3,2)
(4,0), (4,1), (4,2), (4,3)
(5,0), (5,1), (5,2), (5,3), (5,4)
(i.e., nonCombinable contains all the underlined pairs), then again we conclude that we only need 3 states, but this time the states can be described as
0 or 1 or 3
2 or 4
5
Another possibility, of course, is that after we have executed the algorithm, all possible pairs have been added to nonCombinable. In this case, we conclude that no states can be combined, and the original FA is already as simple as possible.
Your program should accept as input a string describing an FA (details below) and produce as output as many lines as there are states in the minimized FA, each line containing the states of the original FA that were combined into one.
The way a string will describe an FA is as follows: it will contain a number of ints, separated by one or more spaces. The first number is the total number n of states in the FA (which are to be thought of as numbered from 0 to n-1). After that are the 2*n numbers f(0,0), f(0,1), f(1,0), f(1,1), f(2,0), f(2.1), ..., f(n-1,0), f(n-1,1) (where f is the transition function, as explained above). Finally the last numbers in the string are the numbers of the accepting states. There may conceivably be none (in which case the FA obviously does not accept any sequences of inputs), and there may conceivably be as many as n (in which case the FA accepts every sequence of inputs); more likely, there will be at least one but fewer than n.
For example: in the case of the FA described above with six states, the input string would look like
6 1 2 0 3 5 3 4 2 1 3 0 3 4 5
and the output should look like
0 1
2 3
4 5
Suggestions. Use a class Pair (sort of like Point) having two int variables, a constructor with two int parameters, and two accessor methods getFirst() and getSecond(), which return the first and second numbers in the pair, respectively. (As we have seen above, (1,0) and (0,1) are really the same pair. For this reason, it would be appropriate for the constructor to interchange the two numbers if necessary so that the larger comes first.) Use two classes IntSet and PairSet representing sets of ints (in this application, sets of states) and sets of pairs. In each case it is sufficient to use a default constructor that initializes the set to have no elements. Appropriate methods in both classes include the following. (I've shown the parameters as ints, but in the case of PairSet they would be Pairs.)
add(int i) // add the element i to the set (if it's already there, do nothing)
delete(int i) // delete the element i from the set (if it isn't in the set, do nothing)
isElement(int i) // returns true if i is an element of the set, false otherwise
firstElement() // returns the first element of the set, or -1 if the set is empty
// (in the case of Pair, an appropriate return value if the set is empty is null)
nextElement(int i) // returns the element of the set that comes after i (if there is one), -1 otherwise
numElements() // returns the number of elements of the set.
print() // prints the elements of the set (useful for debugging purposes)
(Note: the firstElement and nextElement methods should be thought of as analogous to StringTokenizer; they simply provide a way of processing all the elements of a set, one at a time. The specific order in which the elements are processed doesn't really matter---the only important thing is that when used appropriately the methods allow you to do something with each element of the set.)
A good way to represent a set of ints in this program is to use a boolean array with n elements, where n is the number of states in the FA. So the elements of the array go from 0 through n-1. The ith element will be true if the integer i is in the set, false otherwise. So, for example, the way to do add(i) is simply to make the ith element true, provided of course that i is within the appropriate range. To do delete(i), make the ith element false.
A good way to represent a set of Pairs is to use a 2-dimensional boolean array with n rows and n columns, where n is the number of states. (Actually, this is somewhat wasteful, since the only positions in the array that we ever need to use are positions [j] where i>j, but all it means is that we're allocating approximately twice as much space as we need, so it's not terrible.). Note: the fact that we use only the positions [j] for which i>j is the reason for making sure that the Pair constructor always puts the larger number first. If it didn't do this, we could easily make mistakes---for example, add a Pair (i,j) to a set and later conclude by looking at the [j] position of the array that the pair is not in the set.
A good way to represent the transition function of the FA is to use an array f of type int[n][2] , where for example f[0] is the number written f(i,0) above.
Use a class Fa. Instance variables include an int numStates, an IntSet accepting, and an int array for the transition function. The constructor takes a string parameter. You can decide what methods are appropriate in order to do the minimization. Include a method minimize(), but do not allow it to get too big---have it call smaller helper methods. When I did it, I found it helpful to use three sets of Pairs: allPairs (containing all the pairs (i,j) for which 0<=j < i < numStates), combinable, and nonCombinable. In the initial phase of the minimization, we go through all the pairs and for each one, add it to nonCombinable if one of the numbers is an accepting state and the other isn't, and otherwise add it to combinable. Then we make a sequence of passes. In each pass, we go through every pair in combinable, and for each one, say (i,j), test it as above using the transition function, to see whether it should be deleted from combinable and added to nonCombinable. This continues until we do a pass in which no pairs are moved. When we've finished the passes, we then just have to figure out how to use the set nonCombinable (or the set combinable) in order to produce the appropriate output.
The class Pair should be more or less a triviality. I suggest that you then write the class IntSet and test it, then write the class PairSet and test it, and finally, write the Fa class along with a class FaTest containing the main method.
Your main program should allow a user to input a file name, and it should then read a sequence of strings from that file, each string representing another data item (i.e., another FA). You can add this feature at the very end; in the development of the program, you can just use a main program with two lines, such as
Fa m = new Fa("6 1 2 0 3 5 3 4 2 1 3 0 3 4 5");
m.minimize();
Conrad R.
I'll give it a shot (although your assignment was already due).
I always think of a FA as a graph, with the nodes of the graph representing the possible states, and the edges of the graph the transitions between the states. In this assignment, you no there is always exactly two edges leaving every state, one labelled 0 and one labelled 1.
Now, for a series on inputs, you traverse the graph, following the edges labelled the same as the input. You can think of the edge as the transition function f(); So if there is a state q connected with a state r via a edge labelled 1, you get:
f(q, 1) = r.
For each series of inputs, you'll have a starting state and a ending state.
Regarding accepting states.
Each FA can have 0 ore more (but atmost n, where n is the total number of states) of states that are called accepting states. What this means is that for any series of inputs, if the final state is in the set of accepting states, then the FA accepts the series of inputs.
Regarding your assignment.
The assignment is relatively simple, but it can get tricky. What you have to do is receive the input string describing a FA. You then have to find the states that are redundant, i.e. if two states always give the same answer for a series of inputs.
for the example input string:
6 1 2 0 3 5 3 4 2 1 3 0 3 4 5
you get:
6 distinct states (0..5)
f(0,0) = 1 | f(0,1) = 2
f(1,0) = 0 | f(1,1) = 3
f(2,0) = 5 | f(2,1) = 3
f(3,0) = 4 | f(3,1) = 2
f(4,0) = 1 | f(4,1) = 3
f(5,0) = 0 | f(5,1) = 3
and 4 and 5 are you're accepting states.
The method described requires you to test every possible pair of (distinct) states. You keep a list of pairs that cannot be combined, which you initialize to all the pairs of states, where one state is accepting and one not. (watch out for the boundary case, when there are no accepting states, you'll end up with an initial empty non-combinable set)
The initial Non-combinable set will have the following pairs (basically every pair with either a 4 or a 5, but not both, it guarantees that one state is accepting (4/5) and the other not, i.e. they cannot be combined because they produce different answer (per definition)) :
(0,4)
(1,4)
(2,4)
(3,4)
(0,5)
(1,5)
(2,5)
(3,5)
For each of the pairs of states not yet in the set of non-combinable pairs, you do the following:
(assume p and q are not yet in the non-combinable set)
for each input i do
1. Compute f(p,i) = x, f(q,i) = y;
2. If (x,y) is in the non-combinable set, the p and q must be as well
endfor
You break out of that loop when all the pairs are in the non-cominable set, or when you did not add a pair for that iteration.
At the end, the pairs not in the non-combinable set are redudant, and that is your answer.
Hope this help. Don't overcomplicate it, its supposed to be simple. If it helps, draw a graph, follow the edges etc. to get a feel for the FA
I always think of a FA as a graph, with the nodes of the graph representing the possible states, and the edges of the graph the transitions between the states. In this assignment, you no there is always exactly two edges leaving every state, one labelled 0 and one labelled 1.
Now, for a series on inputs, you traverse the graph, following the edges labelled the same as the input. You can think of the edge as the transition function f(); So if there is a state q connected with a state r via a edge labelled 1, you get:
f(q, 1) = r.
For each series of inputs, you'll have a starting state and a ending state.
Regarding accepting states.
Each FA can have 0 ore more (but atmost n, where n is the total number of states) of states that are called accepting states. What this means is that for any series of inputs, if the final state is in the set of accepting states, then the FA accepts the series of inputs.
Regarding your assignment.
The assignment is relatively simple, but it can get tricky. What you have to do is receive the input string describing a FA. You then have to find the states that are redundant, i.e. if two states always give the same answer for a series of inputs.
for the example input string:
6 1 2 0 3 5 3 4 2 1 3 0 3 4 5
you get:
6 distinct states (0..5)
f(0,0) = 1 | f(0,1) = 2
f(1,0) = 0 | f(1,1) = 3
f(2,0) = 5 | f(2,1) = 3
f(3,0) = 4 | f(3,1) = 2
f(4,0) = 1 | f(4,1) = 3
f(5,0) = 0 | f(5,1) = 3
and 4 and 5 are you're accepting states.
The method described requires you to test every possible pair of (distinct) states. You keep a list of pairs that cannot be combined, which you initialize to all the pairs of states, where one state is accepting and one not. (watch out for the boundary case, when there are no accepting states, you'll end up with an initial empty non-combinable set)
The initial Non-combinable set will have the following pairs (basically every pair with either a 4 or a 5, but not both, it guarantees that one state is accepting (4/5) and the other not, i.e. they cannot be combined because they produce different answer (per definition)) :
(0,4)
(1,4)
(2,4)
(3,4)
(0,5)
(1,5)
(2,5)
(3,5)
For each of the pairs of states not yet in the set of non-combinable pairs, you do the following:
(assume p and q are not yet in the non-combinable set)
for each input i do
1. Compute f(p,i) = x, f(q,i) = y;
2. If (x,y) is in the non-combinable set, the p and q must be as well
endfor
You break out of that loop when all the pairs are in the non-cominable set, or when you did not add a pair for that iteration.
At the end, the pairs not in the non-combinable set are redudant, and that is your answer.
Hope this help. Don't overcomplicate it, its supposed to be simple. If it helps, draw a graph, follow the edges etc. to get a feel for the FA
Kobus Brümmer
__________________
"On résiste à l'invasion des armées; on ne résiste pas à l'invasion des idées" - Victor Hugo
__________________
"On résiste à l'invasion des armées; on ne résiste pas à l'invasion des idées" - Victor Hugo
