Finite State Machines
These notes will stay away from formal definitions and proofs, and you are referred to the text for
those. The notes will provide intuition and perspective, which can be an obstacle in trying to read any
material like this.
A finite state machine is a kind of very limited type of computation that has no memory or data
structure except for what you can encode directly into the machine. Every FSM looks like a directed graph where the nodes are called states and the edges are called transitions. The edges are labeled
with symbols of the alphabet, and we run the machine by reading the input one symbol at a time from
left to right, and following the transitions in the graph. We start at a designated start node. When we
are finished reading the string, we decide whether or not we accept that string (answer ‘yes’)
depending on the state that we end up in. If the state is marked final, then we say yes, otherwise no.
Any set of strings accepted by an FSM is called a regular set.
Examples of Regular sets for the alphabet {0,1}.
a. Even number 1’s.
b. Strings containing 101.
c. Even number of 0’s and contains 101.
d. Even number of 0’s or contains 101.
e. All strings.
f. Divisible by three as a binary number.
g. Every one has at least two zeros that follow it.
h. Not divisible by three.
i. A finite set.
j. Second symbol not a one.
k. Some two zeros are separated by a number of symbols that is a multiple of three.
l. End with 00 or 01.
These examples will be done in class and will teach four important lessons:
1. To design FSM’s, give semantic information to the states.
2. Closure properties of a class of sets, help identify sets in the class. Constructive
closure proofs provide actual FSM’s for these sets.
3. Equivalence of FSM variations provides us with high-level tools for designing FSM’s.
4. There is more than one FSM to recognize a set, but there is a unique one with the
minimum number of states.
FSM’s are under complement (h), union (c), intersection (d) and reverse (l). We will explain the first
three in general with examples in class. The proof of the fourth has a bug that will motivate the
following variation of an FSM. Are FSM’s closed under double? That is double(L) is the set of all
strings xx where x is in L? Note interestingly that FSM’s are closed under half(L).
These notes will stay away from formal definitions and proofs, and you are referred to the text for
those. The notes will provide intuition and perspective, which can be an obstacle in trying to read any
material like this.
A finite state machine is a kind of very limited type of computation that has no memory or data
structure except for what you can encode directly into the machine. Every FSM looks like a directed graph where the nodes are called states and the edges are called transitions. The edges are labeled
with symbols of the alphabet, and we run the machine by reading the input one symbol at a time from
left to right, and following the transitions in the graph. We start at a designated start node. When we
are finished reading the string, we decide whether or not we accept that string (answer ‘yes’)
depending on the state that we end up in. If the state is marked final, then we say yes, otherwise no.
Any set of strings accepted by an FSM is called a regular set.
Examples of Regular sets for the alphabet {0,1}.
a. Even number 1’s.
b. Strings containing 101.
c. Even number of 0’s and contains 101.
d. Even number of 0’s or contains 101.
e. All strings.
f. Divisible by three as a binary number.
g. Every one has at least two zeros that follow it.
h. Not divisible by three.
i. A finite set.
j. Second symbol not a one.
k. Some two zeros are separated by a number of symbols that is a multiple of three.
l. End with 00 or 01.
These examples will be done in class and will teach four important lessons:
1. To design FSM’s, give semantic information to the states.
2. Closure properties of a class of sets, help identify sets in the class. Constructive
closure proofs provide actual FSM’s for these sets.
3. Equivalence of FSM variations provides us with high-level tools for designing FSM’s.
4. There is more than one FSM to recognize a set, but there is a unique one with the
minimum number of states.
FSM’s are under complement (h), union (c), intersection (d) and reverse (l). We will explain the first
three in general with examples in class. The proof of the fourth has a bug that will motivate the
following variation of an FSM. Are FSM’s closed under double? That is double(L) is the set of all
strings xx where x is in L? Note interestingly that FSM’s are closed under half(L).
No comments:
Post a Comment