Computer Science
Finite Automata
Finite Automata are abstract machines used to model and analyze the behavior of systems with a finite number of states. They are widely used in computer science for tasks such as lexical analysis, pattern matching, and parsing. Finite Automata operate by transitioning between states based on input symbols, making them valuable tools for understanding and solving computational problems.
Written by Perlego with AI-assistance
Related key terms
1 of 5
11 Key excerpts on "Finite Automata"
eBook - PDF- Michael Sipser(Author)
- 2012(Publication Date)
- Cengage Learning EMEA(Publisher)
The language of a formal definition is somewhat arcane, having some simi-larity to the language of a legal document. Both need to be precise, and every detail must be spelled out. A finite automaton has several parts. It has a set of states and rules for going from one state to another, depending on the input symbol. It has an input al-phabet that indicates the allowed input symbols. It has a start state and a set of accept states. The formal definition says that a finite automaton is a list of those five objects: set of states, input alphabet, rules for moving, start state, and accept states. In mathematical language, a list of five elements is often called a 5-tuple. Hence we define a finite automaton to be a 5-tuple consisting of these five parts. We use something called a transition function , frequently denoted δ , to de-fine the rules for moving. If the finite automaton has an arrow from a state x to a state y labeled with the input symbol 1 , that means that if the automaton is in state x when it reads a 1 , it then moves to state y . We can indicate the same thing with the transition function by saying that δ ( x, 1 ) = y . This notation is a kind of mathematical shorthand. Putting it all together, we arrive at the formal definition of Finite Automata. DEFINITION 1.5 A finite automaton is a 5-tuple ( Q, Σ ,δ,q 0 ,F ) , where 1. Q is a finite set called the states , 2. Σ is a finite set called the alphabet , 3. δ : Q × Σ -→ Q is the transition function , 1 4. q 0 ∈ Q is the start state , and 5. F ⊆ Q is the set of accept states . 2 1 Refer back to page 7 if you are uncertain about the meaning of δ : Q × Σ -→ Q . 2 Accept states sometimes are called final states . Copyright 2012 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).
- Jiacun Wang(Author)
- 2016(Publication Date)
- Chapman and Hall/CRC(Publisher)
The concatenation of zero string is and the concatenation of one string is the string itself. A finite automaton can be thought as a device or a machine with a finite number of internal states . Thus, any machine qualifies as a finite automaton. Finite Automata have been used to model physical and natural phenomena by biologists, psychologists, mathematicians, engineers, and computer scientists. The first formal use of finite state systems, viz. the neural nets, was made by two physiologists Warren McCul-loch and Walter Pitts in 1943 for studying nervous activity [10]. These were later shown to be equivalent to Finite Automata by S.C. Kleene [8]. Kleene also derived the regular expressions for representing regular languages—the languages accepted by Finite Automata. G.H. Mealy [12] and E.F. Moore [13] generalized these to transducers by introducing what are now known as the Moore and the Mealy machines. They are finite state machines with output. Automata theory has been used in a variety of situations. Automata have been applied in areas like lex-ical analysis in programming language compilation [1], circuit designs [2], text editing, pattern matching [9], and many more. It has also been used to study specific recombinant behaviors of DNA [6]. In this chapter, we study an abstraction of these machines regarded as computing devices. Generally, computability theory deals with devices which have no bounds on the space and time utilized. One such example is the Turing machine . The finite automaton that we study is a weak form of a computing machine with limited computing power. We now introduce deterministic Finite Automata. 1.2 Deterministic Finite Automata A deterministic finite automaton (DFA) consists of a finite input tape with cells that hold symbols from some input alphabet . There is a tape-head that scans or reads the content of a cell at any given instant.
eBook - PDF- Bozzano G Luisa(Author)
- 2014(Publication Date)
- Elsevier Science(Publisher)
Indeed a finite automaton can be viewed as a machine model which is as elementary as possible in the sense that the machine has a memory size which is fixed and bounded, independently of the size of the input. The number of possible states of such a machine is itself bounded, whence the notion of a finite-state machine. The historical origin of the finite-state model itself can of course be traced back much earlier to the beginning of this century with the notion of a Markov chain. In fact, a Markov chain is the model of a stochastic process in which the probability of an event only depends on the events that happened before at a bounded distance in the past. Since the origins, the theory of Finite Automata has developed, stimulated both by its possible application and by its inner mathematical orientations. In an early stage, Finite Automata appeared as a development of logical circuits obtained by introducing the sequentiality of operations. This lead to the notion of sequential circuits which is still of interest in the field of circuit design. But the main present applications of Finite Automata are related with text processing. For example, in the phase of the compiling process, known as lexical analysis, the source program is transformed according to simple operations such as comments removal, or parsing of identifiers and keywords. This elementary processing is generally performed by algorithms that are really Finite Automata and can usefully be designed and handled by the methods of automata theory. In the same way, in natural language processing, Finite Automata, often called transition networks, are used to describe some phases of the lexical analysis. These applications of automata to text processing have a natural extension to subjects as text compression, file manipulation or, more remotely, to the analysis of long sequences of molecules met in molecular biology. Other applications of Finite Automata are related to the study of parallel processes.
- Song Y Yan(Author)
- 1998(Publication Date)
- World Scientific(Publisher)
In artificial intelligence, for example, they are employed to model both behavioral situations and intelligent systems, including game playing, human intelligence, machine learning, nervous system activity, and robotic motion systems. 100 Chapter 2. Formal Languages and Automata An automaton whose output is limited to a simple answer yes or no is called a ( decision) problem solver or a language accepter. On an input with a string, the accepter either accepts (recognises) the string or rejects it. A more general automaton, capable of producing strings of symbols as output, is called a function transducer. There are essentially two different types of automata: deterministic au-tomata and nondeterministic automata. In deterministic automata, each move is uniquely determined by the current internal state, the current input symbol and the information currently in the temporary storage. On the other hand, in nondeterministic automata, we cannot predict the exact future behaviour of a automaton, but only a set of possible actions. One of the very important objec-tives of this book is actually to study the relationship between deterministic and nondeterministic automata of various types (e.g., Finite Automata, push-down automata, and Turing machines). 2.2 Finite Automata and Regular Languages Finite-State Automata, or Finite Automata (FA) for short, are the simplest automata (see Figure 2.2). In this section we shall study the basic concepts and Input File [ Finite State Control Unit Figure 2.2: Finite Automaton results of Finite Automata (both deterministic and non-deterministic), and the properties of regular languages, with an emphasis on the relationship between Finite Automata and regular languages.
No longer available |Learn more- (Author)
- 2014(Publication Date)
- Learning Press(Publisher)
________________________ WORLD TECHNOLOGIES ________________________ Chapter 4 Automata Theory and Quantum Computer Automata theory An example of automata and study of mathematical properties of such automata is automata theory In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these abstract machines. These abstract machines are called automata. The figure at right illustrates a finite state machine, which is one well-known variety of automaton. This automaton consists of states (represented in the figure by circles), and transitions (represented by arrows). As the automaton sees a symbol of input, it makes a transition (or jump ) to another state, according to its transition function (which takes the current state and the recent symbol as its inputs). ________________________ WORLD TECHNOLOGIES ________________________ Automata theory is also closely related to formal language theory, as the automata are often classified by the class of formal languages they are able to recognize. An automaton can be a finite representation of a formal language that may be an infinite set. Automata play a major role in compiler design and parsing. Automata Following is an introductory definition of one type of automata, which attempts to help one grasp the essential concepts involved in automata theory. Informal description An automaton is supposed to run on some given sequence or string of inputs in discrete time steps. At each time step, an automaton gets one input that is picked up from a set of symbols or letters , which is called an alphabet . At any time, the symbols so far fed to the automaton as input form a finite sequence of symbols, which is called a word . An automaton contains a finite set of states. At each instance in time of some run, automaton is in one of its states.
eBook - PDF- Mark V. Lawson(Author)
- 2003(Publication Date)
- Chapman and Hall/CRC(Publisher)
Chapter 1 Introduction to Finite Automata The aim of this chapter is to set out the basic definitions and ideas we shall use throughout this book. In particular, we explain what we mean by a finite automaton and the language recognised by a finite automaton. Background results from discrete mathematics are outlined in the Appendix. 1.1 Alphabets and strings Most people today are familiar with the idea of digitising information; that is, converting information from an analogue or continuous form to a discrete form. For example, it is well-known that computers deal only in 0’s and l ’s, but users of computers do not have to communicate with them in binary; they can interact with the computer in a great variety of ways. For example, voice recognition technology enables us to input data without using the keyboard, whereas computer graphics can present output in the form of animation. But these things are only possible because of the underlying sequences of 0 ’s and l ’s that encode this information. We begin this section therefore by examining sequences of symbols and their properties. Information in all its forms is usually represented as sequences of symbols drawn from some fixed repertoire of symbols. More formally, any set of symbols A that is used in this way is called an alphabet, and any finite sequence whose components are drawn from A is called a string over A or simply a string.1 We call the elements of an alphabet symbols or letters. The number of symbols in an alphabet A is denoted by | A |. The alphabets in this book will always be finite. 1T he term word is often used instead of string. 1 2 CHAPTER 1. INTRODUCTION TO Finite Automata Examples 1.1.1 Here are a few examples of alphabets you may have encoun-tered. (1) An alphabet suitable for describing the detailed workings of a computer is { 0 , 1 }. (2) An alphabet for representing natural numbers in base 10 is { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 }.
eBook - PDF- Thomas Koshy(Author)
- 2004(Publication Date)
- Academic Press(Publisher)
Chapter 11 Formal Languages and Finite-State Machines Time as he grows old teaches many lessons. — AESCHYLUS T he study of finite-state machines began with the neural networks investigations of Warren S. McCulloch and Walter Pitts in 1943. Today paradigms of finite-state constructs can be seen everywhere: turnstiles, traffic signal controllers, automated teller machines, auto-mated telephone service, garage door openers, household appliances, and coin-operated machines such as vending machines and slot machines. Finite-state machines significantly assist the study of formal languages; for example, a machine can be designed (or a program developed) that determines if an input string over the alphabet {a,b} contains abba as a substring. (The string babaabbaba does, while abaaba does not.) This type of machine produces no output, but instead tells whether or not the input string has a certain property. (Example 11.26 explores this.) Some machines, however, produce output values. For instance, adding two binary numbers requires the input of two numbers, and yields their sum as the output (see Example 11.42). Such a machine, a finite-state automaton, is described in Section 11.4. Since all finite-state automata must recognize particular languages, for-mal languages and types of grammars become important. This chapter explores formal languages, and how automata and formal languages are related, as well as other interesting questions such as: • How do we determine if a string of characters contains a certain substring? • How do we simulate an automatic teller machine? 733 734 Chapter 11 Formal Languages and Finite-State Machines • Can we develop a program that accepts two binary numbers, adds them bit by bit, and outputs their sum? • What sort of languages are accepted by finite-state automata? 11.1 Formal Languages We now continue our study of formal languages, begun in Section 2.1. The language of sets plays an important role in the study, as we saw in Chapter 2.
- Harry Lewis, Rachel Zax(Authors)
- 2019(Publication Date)
- Princeton University Press(Publisher)
Chapter 19 Finite Automata In Chapter 15, we showed how to model the behavior of a computer pro-gram as a directed graph, with the vertices representing states. In this chapter, we focus on a very simple model for a computer, the finite auto-maton , also known as the finite state machine . The finite automaton is an unrealistic model for an entire computer system, but an extremely useful model for small parts of a computer system. Let’s begin with an example. Suppose we wanted to design a computer to decide whether an input string of symbols from the two-symbol alphabet = { a , b } has an odd number of occurrences of a and an odd number of occurrences of b . We could use a device with the state space of Figure 15.5 (page 153), by simply counting up the numbers of occurrences of a and b and then checking at the end to see whether those numbers are even or odd. But that would be overkill. It would require registers capable of holding integers of arbitrarily large size, when just two bits of information need to be remem-bered. It suffices to know whether the number of occurrences of a seen so far is even or odd, and whether the number of occurrences of b seen so far is even or odd. This can be done in a state space with only four states, as shown in Figure 19.1. We have slightly embellished the notion of state space as previously defined, numbering the states 0, 1, 2, and 3, designating state 0 as the start state by marking it with the > character, and double-circling state 3 to indicate that it is what we will call a “final” or “accepting” state. A finite automaton “accepts” an input string by reaching a final state after starting in the start state and reading the entire string. a 0 > 2 3 1 a b b b b a a Figure 19.1. A finite automaton accepting all strings with an odd number of occurrences of a and an odd number of occurrences of b .
eBook - PDF- Andrei Kelarev(Author)
- 2003(Publication Date)
- CRC Press(Publisher)
Automata and Languages Chapter 3 3.1 Finite State Automata Finite Automata are well-known tools of language theory. Every finite state automaton accepts or recognizes a certain language. Before a formal defi-nition, let’s take a look at the following example of Australian public pay- telephone illustrated as a finite state automaton. The telephone accepts 5c, 10c and 20c coins, and allows a call to be made for 40c. It has 9 states, go? 05? 0 io? 015? 020? 025? 030? 035? 040? where the subscript indicates the amount of money received. The state qo, when the customer begins to insert coins, is called the initial state (or start state); the state 940 , when the phone allows a call, is the terminal state. The telephone accepts or recognizes any sequence of coins that adds up to precisely 40c. It can be described pictorially with a transition diagram displayed in Figure 3.1. The language accepted by the machine is the following set of input sequences: {( 20 , 20 ), ( 20 , 10 , 10 ), ( 20 , 10 , 5 , 5 ), ( 20 , 5 , 10 , 5 ), ( 20 , 5 , 5 , 10 ), ( 20 , 5 , 5 , 5 , 5 ), ( 10 , 20 , 10 ), ( 10 , 20 , 5 , 5 ), ( 10 , 10 , 20 ), ( 10 , 10 , 10 , 10 ), 143 144 Chapter 3. Finite Automata Figure 3.1: Australian pay-phone (10,10,10,5,5), (10,10,5,10,5), (10,10,5,5,10), (10,10,5,5,5,5), (10,5,10,10,5), (10,5,10,5,10), (10,5,5,10,10), . . . , (5,5,5,5,20), (5,5,5,5,10,10), (5,5,5,5,10,5,5), (5,5,5,5,5,10,5), (5,5,5,5,5,5,10), (5,5,5,5,5,5,5,5)} which correspond to walks from the initial to the terminal state. A similar coin telephone accepting dimes and quarters and making a call for $1 is shown in Figure 3.2. A finite state automaton or acceptor is a 5-tuple (Q,X,&,qo,T), where • Q is a set of states; • X is the input alphabet; 95 C l --20 2° ^V>^ / 5 10 9 3 5 ^ 5 ^ 5 ~ ^ f t 5 10 • S is the next-state function or transition function; • qo is the start state or initial state; • T is the set of terminal states or final states.
eBook - PDFDiscrete Mathematics
Proof Techniques and Mathematical Structures
- R C Penner(Author)
- 1999(Publication Date)
- WSPC(Publisher)
400 Chapter 9 Languages and Finite State Automata the letter a for each a € A. In other words, we must describe a function A->S S oh> (d a :S->S). For another point of view on this function, define the associated transition function d:AxS->S (a, s) i-» d a (s). Of course, the transition function itself determines the function A -> S s according to the rule d a {s) = d(a, s), so the two points of view are entirely equivalent. It is customary to consider the transition function d : A x S —► S rather than the associated function A -* S s as a description of the rules for the evolution of states of our machine. Turning from this motivational image of a machine to more precise state-ments, we define a finite state automaton or simply an automaton to be a quintuple (5, A, d, Y, so), where • S is a finite set called the state set • A is an alphabet as before. • d: Ax S —> S is a function called the transition function. • Y is a (possibly empty) subset of S called the set of accept states, success states, or final states. • so is a distinguished element of 5 called the initial state or start state. There is actually a generalization of this definition which we shall give in the next section, and we shall later refer to a finite state automaton (5, A, d, Y, SQ) as above as a deterministic finite state automaton to distinguish it from the generalization, which is called a non-deterministic finite state automaton. Before giving examples, we define a digraph G, called the state diagram of an automaton (S, A, d, Y, SQ), as follows: The vertices of G are labeled by the states S, so there is one vertex v s of G for each s G 5; for each s,t G S, we then adjoin an oriented edge from v s to Vt with the label a G A if d(a, s) = t.
eBook - PDF- Kyle Gorman, Richard Sproat(Authors)
- 2022(Publication Date)
- Springer(Publisher)
1 C H A P T E R 1 Finite-State Machines This is a book about weighted finite-state transducers (WFSTs) and their use in text generation and processing. The WFST formalism synthesizes decades of research into graphs, automata, and formal languages, including lines of research blossoming long before the era of ubiquitous digital computing. The history of finite-state technology stretches back almost a century. Some key theorems and algorithms were discovered—and rediscovered—long before computers became powerful enough to exploit them (see chapter 5 for an example) and in some cases decades have elapsed between discovery and software implementation. Some essential algorithms were not gener- alized until the 1990s or later, as part of efforts—particularly at AT&T Bell Labs, and later at Google—to use WFSTs for scalable automatic speech recognition and text-to-speech synthesis. A few key notions connect these disparate areas of research and application. The first is that of the state machine, a sort of abstract mathematical model of computation of which weighted finite-state transducers are a special case. Such models, first formalized by Turing (1936), are not only the foundation of the theory of computation—quite literally, the study of what it means to compute—but also inspired the creation of ENIAC, the first general-purpose digital computer, a decade later. The second is that of formal languages. While the origins of formal language theory can be traced at least as far back as Thue (1914), perhaps the most im- portant contribution is a study by Kleene (1956) first circulated in 1951. Kleene’s study springs from an obscure goal: the formal characterization of the expressive capacity of “nerve nets”, a primitive form of artificial neural network proposed by McCulloch and Pitts (1943) a few years prior.
Index pages curate the most relevant extracts from our library of academic textbooks. They’ve been created using an in-house natural language model (NLM), each adding context and meaning to key research topics.
