New Page 1
Welcome to basicsofcomputer.com

Home » Computer Dictionary » Letter F » Finite-State Automaton (FSA; finite-state machine) Definition/Meaning

# Finite-State Automaton (FSA; finite-state machine) Definition/Meaning:

A simple kind of automaton. The input string is read once from left to right, looking at each symbol in turn, At any time the FSA has some internal state, which changes after each input symbol is read. The new state depends firstly on the symbol just read and secondly on the current state. An FSA is therefore determined by a function ƒ from I x Q to Q, where I is the set of possible input symbols, Q is the set of states, and I x Q is the Cartesian product of I and Q. Q must be finite, hence the name FSA.

The function ƒ is called a state transition function. It is commonly represented either by a table or by a directed graph, known respectively as a state transition table and a state transition diagram. The figure shows two equivalent representations in which

I = (a,b,c),

Q =  (1,2,3,4)

In this example,

ƒ(a,1) = 2

ƒ(c,4) = 4, etc.

ƒ extends to strings in the obvious manner:

in the example,

ƒ(b,c,2) = 4,

ƒ(aaa,3) = 1, etc.

Let Q be divided into accepting stales and rejecting states, and let q0 be some member of Q (referred to as the start state). The language recognized by the FSA is the set of all w such that

ƒ(w,q0)

is an accepting state, i.e. the set of all strings that take the start state to an accepting state. For example, in the FSA shown in the figure let q0 be 1 and let 4 be the only accepting state; the language recognized is then the set of all strings over {a,b,c} that somewhere contain abc as a substring.

A generalization is to allow more than one state to which the FSA can move, for a given input symbol and current state. This gives a nondeterministic FSA. The input string is then accepted if there is some sequence of choices of moves leading to an accepting state. Such a machine can always be converted to a deterministic one recognizing the same language.

## Near by Terms:

 Fiber Optics Transmission System Fibonacci Search Fibonacci Series Field Field-Effect Transistor (FET) Field-Programmable Devices FIFO or fifo File File Activity Ratio File Descriptor File Directory File Maintenance File Management File Mark File Organization File Processing File Protection File Reel File System File Transfer File Updating Fill Character Filter Filtering Find Finite Automaton Finite-Difference Method Finite-Element Method Finite Field (Galois field) Finite-Length Arithmetic (fixed-length arithmetic) Finite Sequence (list) Finite Set Finite-State Automaton (FSA; finite-state machine) FIPS Fire Codes Firmware First Fit First Generation of Computers First in First Out Fixed and Exchangeable Disk Store Fixed-Base System Fixed Head of a Disk Drive Fixed-Length Arithmetic Fixed-Length Code Fixed-Point Notation Fixed-Point Theorem Fixed-Radix System (fixed-base system) Fixed Word Length Computer

New Page 1

Basic Computer Science

 » The Age of Information » Types of Computer and Digital Age » Input and Output Devices » Storage Devices Of Computer » Central Processing Unit » Software: The Power Behind The Power » Data Communication and Computer Networks » The Nature Of Information » The System Theory » Transaction Processing System (TPS) and Management Information System (MIS) » » Expert System (ES) and Office Information System (OIS)

Operating Systems

 » Introduction to Operating System » Introduction to Process Management » Threads and CPU Scheduling » Process Synchronization in Operating System » Deadlocks » Memory Management in Operating System » Virtual Memory in Operating System » File System Management in Operating System » I/O and Device Management » Security » Linux Operating System

Database Management System

 » Introduction to Database Systems » Database System Architecture » Database Administration and Database Development Process » The Entity-Relationship Model » Semantic Object Model » Logical Database Design and Relational Data Model » Normalization in Database » Transformation of E-R Model into Relational Data Model » Representing Semantic Object Model and Types of Semantic Object Model » Physical Database Design » Introduction to Structured Query Language (SQL) » Implementation of Relational Database and Database Application Design » Client Server Database Systems & Open Database Connectivity (ODBC)