Combinations of states that are considered “dangerous” or that would indicate a failure (e.g., a system going into deadlock) are identified Analysis, some algorithmic and some human, of those state diagrams is performed to see if it is possible to reach any of those undesired states. An FSA “specification” is given for various portions of a complex system. Pushing a bit further on this theme, model checking is an approach to validating complex systems, particularly concurrent systems. The very fact that the notation for such state diagrams is part of an industry standard notation should give you a sense of how common it is for developers to use FAs as a basis for reasoning about software. But the kinship to the formal model of FAs should be pretty obvious. The notation used in this diagram is that of a UML state diagram. When the I/O operation is completed, the process returns to the Ready state until the scheduler decides to give it some more CPU time. In the latter case, the process moves into a Blocked state, surrendering the CPU back to the schedule. It stays in this state until either the scheduler decides to take back the CPU (because a “time slice” has expired) or because the process has initiated an I/O operation that, compared to the CPU speed, may take a substantial amount of time. At that moment, the process starts Running. Therefore newly started processes start in a Ready state and have to wait until the OS scheduler assigns a CPU to them. Most operating systems will be running more processes than can be simultaneously accommodated on the number of physical CPUs. Here, for example, is a state diagram summarizing the behavior of processes in a typical operating system. One worth mentioning is the Mealy machine, which adds to each state transition an optional string to be emitted. There are some common variations that allow us to “do” things with an FA without substantially altering the computation power beyond that of a regular FA. This chapter has looked at a very “pure” form of FSA. If you don’t know what set of strings would take you to a state, you should consider carefully whether you want or need that state at all. Try to only introduce new states into an FSA because they have a specific purpose. $\delta = \$, i.e., strings that have an “extra” 10 that might or might not later be shown to be part of a 101 choice. $q_0$ is, well, $q_0$ because we chose to use that matching label for the state. These are the characters that we can supply as input. These are simply labels for states, so we can use any symbol that is convenient. (We will choose to always write the characters on either side of the river in alphabetic order.) We want to end up with everything on the other side of the river: |CDGM.įor example, for the FA shown here, we would say that: We can model this by labeling situations using the characters M C G D | to denote the man, the cabbage, the goose, the dog, and the river, respectively.įor example, we start with everyone on one side of the river: CDGM|. How can the man get across the river with all his items intact? If he leaves the dog alone on either shore with hte goose, the dog will kill the goose. If he leaves the goose alone on either shore with the cabbage, the goose will eat the cabbvage. The boat is so small that he can take only himself and one of his accompanying items at a time. On the shore in front of him is a small rowboat. He has with him a head cabbage, a goose, and a dog. 2 An Opening ExampleĪ man stands on the side of a small river. It is, however, powerful enough to have quite few practical applications, while being simple enough to be easily understood. Not all things that we regard as “computation” can be done with FAs. This is, as we will see, a computation model of somewhat limited power. Some of these states being acceptor or final states. Transitions from state to state are governed. 1 Introductionįinite automata (FA), also widely known as finite state automata (FSA), are a mathematical model of computation based on the ideas ofĪ system changing state due to inputs supplied to it. I will both offer my own commentary on the text as appropriate and will also provide JFLAP files and possibly other study aids to enhance the text’s own examples. These lecture notes are intended to be read in concert with Chapter 2 of the text (Martin). In this chapter, we look at this model and at the languages that they can accept. Finite Automata are a simple, but nonetheless useful, mathematical model of computation.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |