Basic of Finite Automata

Add to Favourites

Post to:

Description
A finite-state machine (FSM) or finite-state automaton (plural: automata), or simply a state machine, is a mathematical model of computation used to design both computer programs and sequential logic circuits. It is conceived as an abstract machine that can be in one of a finite number of states. The machine is in only one state at a time; the state it is in at any given time is called the current state. It can change from one state to another when initiated by a triggering event or condition, this is called a transition. A particular FSM is defined by a list of its states, and the triggering condition for each transition.

The behavior of state machines can be observed in many devices in modern society which perform a predetermined sequence of actions depending on a sequence of events with which they are presented. Simple examples are vending machines which dispense products when the proper combination of coins are deposited, elevators which drop riders off at upper floors before going down, traffic lights which change sequence when cars are waiting, and combination locks which require the input of combination numbers in the proper order.

Finite-state machines can model a large number of problems, among which are electronic design automation, communication protocol design, language parsing and other engineering applications

Type: ppt

Discussion

Presentation Transcript

BASICS OF FINITE AUTOMATA : BASICS OF FINITE AUTOMATA Neenu Prasad

Automaton : Automaton The system in which information is transmitted and used for performing some functions without direct participation of man. Mathematical model of a system with discrete i/p’s and o/p’s System can be in any number of internal configurations on states.

Cont.. : Cont.. Automaton without Memory O/p depends only on the i/p Automaton with Memory o/p depends on i/p and state Deterministic Finite Automata (DFA) The machine can exist in only one state at any given time Non-deterministic Finite Automata (NFA) The machine can exist in multiple states at the same time

Moore and Mealy Machine : Moore and Mealy Machine Moore Machine An automaton in which output depends only on state of the machine. Mealy Machine An automaton in which the output depends on state and the input at any instant of time

Definition : Definition Can be defined analytically by a 5 tuple M={Q,∑, ᶑ , q 0 ,F), Where Q=finite set of states ∑=finite set of inputs called input alphabet ᶑ =mapping or transition function which maps Q x ∑ Q q0 ==> a start state F=set of final states

TRANSITION SYSTEM : TRANSITION SYSTEM Finite directed labeled graph Vertex or represents state Directed edge indicates transition of a state Edges are labeled with inputs Final state is indicated by double centric circles

TRANSITION SYSTEM : TRANSITION SYSTEM q0 q2 b b a b a q1 a a b a b q3 q4

Transition table : Transition table State a b qo q1 q2 q1 q1 q3 q2 q4 q2 q3 q1 q3 q4 q4 q2

Cont.. : Cont.. Here, initial state is q0 Final state is q3 and q4 When qo receives input a,it goes to another state q1,and when the input is b ,it goes to q2.This is indicated as directed labeled edges. This continues for each and every state and at the end moves to final state.This transition with inputs and states are represented in the above transition table

PowerPoint Presentation : THANK YOU