Loading...
Please wait, while we are loading the content...
Similar Documents
Lecture I Finite Automata §1. Regular Sets and Dfa
| Content Provider | Semantic Scholar |
|---|---|
| Author | Yap, Chee-Keng |
| Abstract | We introduce finite automata (deterministic and nondeterministic) and regular languages. Some general concepts and notations are gathered at the end for easy reference. We give an intuitive introduction to state diagrams using the example of an automatic door closer (see figure 1(a)). close (a) (b) open front neither rear,both,neither front,rear,both FRONT REAR Figure 1: (a) Door Plan, (b) State diagram The door can be in one of two states: open or close. There are two sensor pads, one in front and one behind the door. The door opens towards the rear, allowing a person on the front pad to pass through the door. There are 4 sensor inputs, corresponding to the presence or absence of pressure on the pads: front, rear, neither and both. Note that front means " front pad only " , neither means " neither pad " , etc. The state transitions are triggered by sensor inputs, and fully described in figure 1(b). From either state, there is only one input that can trigger a state change: if in the close state, we can only change to open if the input is front. In particular, we do not open the door if there is someone in the rear, as the door can hit that person. Similarly, from the open state, only the neither input can trigger a state change. This representation of the logic using a digraph with labels on edges is called a state diagram. Another example of an smart card wallet. State diagrams can also be formalized as finite automata, a term that emphasizes the finiteness of the number of states. A deterministic finite automata (dfa) is a 5-tuple such that • Q and Σ are finite sets, called the state set and the input alphabet (respectively). |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://cs.nyu.edu/~yap/classes/theory/02s/lect/l1/l.pdf |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
