Free Ebooks Download ! Edhole

of 8
15 views
PDF
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Document Description
1. EDUCATION HOLE PRESENTS THEORY OF AUTOMATA & FORMAL LANGUAGES Unit-II 2. Nondeterministic finite Automata (NFA)…
Document Share
Document Transcript
  • 1. EDUCATION HOLE PRESENTS THEORY OF AUTOMATA & FORMAL LANGUAGES Unit-II
  • 2. Nondeterministic finite Automata (NFA) ................................................................................. 2 Deterministic finite Automata (DFA)........................................................................................ 3 Construction of DFA from NFA and optimization ..............................................................................5 FA with output: Moore machine...........................................................................................................................5 Tracing using Timing Diagrams .........................................................................................................5 Mealy machine and Equivalence ............................................................................................. 7 Applications and Limitation of FA.....................................................................................................7 Automata Simulators .......................................................................................................................8 Nondeterministic finite Automata (NFA) An interesting connection lies between the ideas of this chapter and the theory of finite automata, which is part of the theory of computation (see [462,891]). In Section 2.1, it was mentioned that determining whether there exists some string that is accepted by a DFA is equivalent to a discrete feasible planning problem. If unpredictability is introduced into the model, then a nondeterministic finite automaton (NFA) is obtained, as depicted in Figure 11.8. This represents one of the simplest examples of no determinism in theoretical computer science. Such nondeterministic models serve as a powerful tool for defining models of computation and their associated complexity classes. It turns out that these models give rise to interesting examples of information spaces. Figure 11.8: (a) An nondeterministic finite automaton (NFA) is a state machine that reads an
  • 3. input string and decides whether to accept it. (b) A graphical depiction of an NFA. An NFA is typically described using a directed graph as shown in Figure 11.8b, and is considered as a special kind of finite state machine. Each vertex of the graph represents a state, and edges represent possible transitions. An input string of finite length is read by the machine. Typically, the input string is a binary sequence of 0's and 's. The initial state is designated by an inward arrow that has no source vertex, as shown pointing into state in Figure 11.8b. The machine starts in this state and reads the first symbol of the input string. Based on its value, it makes appropriate transitions. For a DFA, the next state must be specified for each of the two inputs 0 and from each state. From a state in an NFA, there may be any number of outgoing edges (including zero) that represent the response to a single symbol. For example, there are two outgoing edges if 0 is read from state (the arrow from to actually corresponds to two directed edges, one for 0 and the other for ). There are also edges designated with a special symbol. If a state has an outgoing , the state may immediately transition along the edge without reading another symbol. This may be iterated any number of times, for any outgoing edges that may be encountered, without reading the next input symbol. The no determinism arises from the fact that there are multiple choices for possible next states due to multiple edges for the same input and transitions. There is no sensor that indicates which state is actually chosen. The interpretation often given in the theory of computation is that when there are multiple choices, the machine clones itself and one copy runs each choice. It is like having multiple universes in which each different possible action of nature is occurring simultaneously. If there are no outgoing edges for a certain combination of state and input, then the clone dies. Any states that are depicted with a double boundary, such as state in Figure 11.8, are called accept states. When the input string ends, the NFA is said to accept the input string if there exists at least one alternate universe in which the final machine state is an accept state. Deterministic finite Automata (DFA) A DFA represents a finite state machine that recognizes a RE. For example, the following DFA: Recognizes (abc+ )+ . A finite automaton consists of a finite set of states, a set of transitions (moves), one start state, and a set of final states (accepting states). In addition, a DFA has a unique transition for every state-character combination. For example, the previous figure has 4
  • 4. states, state 1 is the start state, and state 4 is the only final state. A DFA accepts a string if starting from the start state and moving from state to state, each time following the arrow that corresponds the current input character, it reaches a final state when the entire input string is consumed. Otherwise, it rejects the string. Let Q be a finite set and let be a finite set of symbols. Also let be a function from Q to Q , let q0 be a state in Q and let A be a subset of Q. We call the elements of Q a state, the transition function, q0 the initial state and A the set of accepting states. Then a deterministic finite automaton is a 5-tuple < Q , , q0 , , A > 1. The set Q in the above definition is simply a set with a finite number of elements. Its elements can, however, be interpreted as a state that the system (automaton) is in. Thus in the example of vending machine, for example, the states of the machine such as "waiting for a customer to put a coin in", "have received 5 cents" etc. are the elements of Q. "Waiting for a customer to put a coin in" can be considered the initial state of this automaton and the state in which the machine gives out a soda can can be considered the accepting state. 2. The transition function is also called a next state function meaning that the automaton moves into the state (q, a) if it receives the input symbol a while in state q. Thus in the example of vending machine, if q is the initial state and a nickel is put in, then (q, a) is equal to "have received 5 cents". 3. Note that is a function. Thus for each state q of Q and for each symbol a of , (q, a) must be specified. 4. The accepting states are used to distinguish sequences of inputs given to the finite automaton. If the finite automaton is in an accepting state when the input ceases to come, the sequence of input symbols given to the finite automaton is "accepted". Otherwise it is not accepted. For example, in the Example 1 below, the string a is accepted by the finite automaton. But any other strings such as aa, aaa, etc. are not accepted. 5. A deterministic finite automaton is also called simply a "finite automaton". Abbreviations such as FA and DFA are used to denote deterministic finite automaton. DFAs are often represented by digraphs called (state) transition diagram. The vertices (denoted by single circles) of a transition diagram represent the states of the DFA and the arcs labeled with an input symbol correspond to the transitions. An arc ( p , q ) from vertex p to vertex q with label represents the transition (p, ) = q . The accepting states are indicated by double circles. Transition functions can also be represented by tables as seen below. They are called transition table.
  • 5. Construction of DFA from NFA and optimization It is to be noted that according to the Kleene's theorem, if a language can be accepted by an FA, then there exists a TG accepting that language. Since, an NFA is a TG as well, therefore there exists an NFA accepting the language accepted by the given FA. In this case these FA and NFA are said to be equivalent to each others. FA with output: Moore machine The goal of FSMs is to describe a circuit with inputs and outputs. So far, we have inputs, that tell us which state we should go to, given some initial, start state. However, the machine generates no outputs. We modify the FSM shown above, by adding outputs. Moore machines add outputs to each state. Thus, each state is associated with an output. When you transition into the state, the output corresponding to the state is produced. The information in the state is typically written as 01/1. 01 indicates the state, while 1 indicates the output. 01/1 is short hand for q1q0 = 01/z = 1 The number of bits in the output is arbitary, and depends on whatever your application needs. Thus, the number of bits may be less than, equal, or greater than the number of bits used to represent the state. Let's look at an example of a Moore machine. In this example, you see two bits for the state and two bits for the output. Thus, when you see 00/01 inside one of the circles, it is shorthand for q1q0 = 00 / z1 z0 = 01. Tracing using Timing Diagrams Given the Moore machine in the previous diagram, and the timing diagram below, you might be asked to determine the state and output.
  • 6. The timing diagram isn't too hard to follow. Basically, you will start off in some state (let's say, 00), and draw the diagram to indicate what happens to the state (q1q0) and to the output (z1z0). You'll notice the input does NOT change at the positive edge. That way, it's easier for you to tell the value of the input at the positive edge. To make it easier to read, I've added the value of x at the positive edge. Thus, the inputs are 1, 1, 0, 1, 1, 0. Let's look at the timing diagram at the first positive edge (drawn with a vertical line). Before the first edge, the state, q1q0 = 00. The input is 1. This should put us in state 01 (i.e., q1q0 = 00), which outputs 11 (i.e., z1z0 = 11). You have to read down the columns. The first column says that the machine is in state 00, with output 01. The second column says that the machine is in state 01, with output 11. The reason the second column says that is due to the input, x, read in at the first positive edge. The input x is 1, which caused the FSM to move from state 00 to state 01. The value of the state and output are placed in the middle, but the really, it's the dark line that tells you when this happens. The state and output changes value on the positive edge (technically, it takes a small, but finite amount of time after the positive edge for the state and output to finally settle down, but we'll draw the diagrams as if it happens instantaneously---even though it doesn't). Here's the rest of the timing diagram.
  • 7. Mealy machine and Equivalence We have two ways to describe a FSM: Mealy and Moore machines. A mathematician might ask are the two machines equivalent. Initially, you might think not. A Mealy machine can have its output depend on both input and state. Thus, if we ignore the state, we should be able to convert a Moore machine to a Mealy machine. It's not so easy to see that you can convert an arbitrary Mealy machine to a Moore machine. It turns out that the two machines are equivalent. What does that mean? It means that given a Moore machine, you can create a Mealy machine, such that if both machines are fed the same sequence of inputs, they will both produce the same sequence of outputs. You can also convert from a Mealy machine to its equivalent Moore machine, and again generate the same outputs given the same sequence of inputs. Actually, to be precise we must ignore one fact about Moore machines. Moore machines generate output even if no input has been read in. So, if you ignore this initial output of the Moore machine, you can convert between one machine and the other. The actual algorithm is beyond the scope of the course. However, the basic idea of converting a Mealy machine to a Moore machine is to increase the number of states. Roughly speaking, if you have a Mealy machine with N states, and there are k bits of input, you may need up to 2k N states in the equivalent Moore machine. Effectively, the new states record information about how that state was reached. Applications and Limitation of FA Each model in automata theory plays important roles in several applied areas. Finite automata are used in text processing, compilers, and hardware design. Context-free grammar (CFGs) are used in programming languages and artificial intelligence. Originally, CFGs were used in the study of the human languages. Cellular automata are used in the field of biology, the most
  • 8. common example being John Conway's Game of Life. Some other examples which could be explained using automata theory in biology include mollusk and pine cones growth and pigmentation patterns. Going further, a theory suggesting that the whole universe is computed by some sort of a discrete automaton is advocated by some scientists. The idea originated in the work of Konrad Zuse, and was popularized in America by Edward Fredkin. Automata Simulators Automata simulators are pedagogical tools used to teach, learn and research automata theory. An automata simulator takes as input the description of an automaton and then simulates its working for an arbitrary input string. The description of the automaton can be entered in several ways. An automaton can be defined in a symbolic language or its specification may be entered in a predesigned form or its transition diagram may be drawn by clicking and dragging the mouse. Well known automata simulators include Turing’s World, JFLAP, VAS, TAGS and SimStudio.
  • We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks
    SAVE OUR EARTH

    We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

    More details...

    Sign Now!

    We are very appreciated for your Prompt Action!

    x