Home » Discrete Mathematics

Finite Automata | Discrete Mathematics

In this article, we will learn about the introduction of finite automata, some components of finite machine and types of finite automata.
Submitted by Prerana Jain, on August 28, 2018

Finite state machine

A finite state machine (FSM) is similar to a finite state automation (FSA) except that the finite state machine "prints" an output using an output alphabet distinct from the input alphabet. The final definition is as follow:

A finite state machine (also called complete sequential machine ) M( A, S, Z, S0, f, g) consists of six points.

  1. A finite set A of input alphabet.
  2. A finite set S of internal state.
  3. A finite set z of output symbol.
  4. An initial state S0 in S.
  5. A next-state function f from S X A into S.
  6. An output function g from S X A into Z.

Components of finite state machine

Input type

The input type is divided into a square and each square contains a single symbol from the input alphabet X. The end squares of the tape contain end markers at the left end and $ at the right end. The absence of end markers in the input tape indicates that there is an infinite length of the tape. The left to right sequence of symbol between the end markers is the input string to be processed.

Reading head

The head examines only one square at a time and can move on square either to the left or to the right. For further analysis are restrict the movement of R head only to the right side.

Finite control

The input to the finite control will be usually symboled under the R-head say a or the present state of the machine say q to give the following output:

  1. A motion of R head along the tape to the next square.
  2. The next state of the finite state machine given by & (q, a).

Transition system

The finite labeled graph in which a state is represented by the vertex or node and the directed edges indicates the transition of a state and the edges are labeled with input/output is known as transition graph or a transition system.

In the normal transition diagram, the initial state is represented by a circle with an arrow pointing towards it, the final state by two concentric circles and the other states are represented by just a circle.

normal transition diagram


Types of finite Automata

There are two types of finite automata:

1) Deterministic finite automata

Some moves of the machine can be uniquely determined by the input symbol and present state. The DFA can be defined with 5 tuples (Q, X, &, q0, F). When,

  • Q - is a finite non-empty set of states.
  • X - is a finite non-empty set of input called input alphabet.
  • & - is a function which maps Q x X into q and is usually called direct transition function. This is the function which describes the change of states driving the transition. This mapping is usually represented by a transition table or a transition diagram.
  • Qo E Q - is the initial state and,
  • F C Q - is the set of final states. It is assumed here that there may be more than one final state.

2) Non- deterministic finite Automata

Some moves of the machine can not uniquely determine by the input symbol and present state. The NDFA can be defined with 5 tuples. (Q, X, f, q0, F). Where,

  • Q - is a finite non-empty set of states.
  • X - is a finite non-empty set of inputs.
  • & - is the transition function mapping from Q x X into 2Q which is the power set of Q, the set of all subset of Q.
  • q0 E Q - is the initial state.
  • F C Q - is the set of final states.

The difference between the deterministic and non- deterministic automata is only in &. For deterministic automation, the outcome is a state i.e. an element of Q for non- deterministic automation the outcome is a subset of Q.

Finite automata






Comments and Discussions

Ad: Are you a blogger? Join our Blogging forum.




Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.