Scribd
Upload
12 views5 pages

Module-1 Finite Automata

Finite Automata (FA) are abstract machines that recognize patterns through a finite number of states based on input symbols, essential for regular languages and applications like compilers and network protocols. The two primary types are Deterministic Finite Automata (DFA), which have a single transition per input symbol, and Non-deterministic Finite Automata (NFA), which can have multiple transitions and allow null moves. Both types are capable of recognizing regular languages, with NFAs being simpler but potentially larger in design compared to DFAs.

Uploaded by

Priyam jay
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
12 views5 pages

Module-1 Finite Automata

Finite Automata (FA) are abstract machines that recognize patterns through a finite number of states based on input symbols, essential for regular languages and applications like compilers and network protocols. The two primary types are Deterministic Finite Automata (DFA), which have a single transition per input symbol, and Non-deterministic Finite Automata (NFA), which can have multiple transitions and allow null moves. Both types are capable of recognizing regular languages, with NFAs being simpler but potentially larger in design compared to DFAs.

Uploaded by

Priyam jay
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Finite Automata (FA)

Finite Automata (FA) are abstract, simple machines in computer science that
recognize patterns by moving between a finite number of states based on input
symbols, forming the basis for regular languages and used in compilers, text
processing, and network protocols.
They operate on a set of states, an alphabet of symbols, a transition function
(rules for state changes), a start state, and accepting states, determining if an
input string belongs to a recognized pattern.
The two main types are Deterministic Finite Automata (DFA) and Non-
deterministic Finite Automata (NFA).

The finite automata can be represented using


i) Input tape - It is a linear tape having some number of cells. Each input
symbol is placed in each cell.

ii) Finite control - The finite control decides the next state on receiving
particular input from input tape. The tape reader reads the cells one by one from
left to right and at a time only one input symbol is read.

1. Deterministic Finite Automata (DFA)


A DFA is represented as {Q, Σ, q, F, δ}. In DFA, for each input symbol, the
machine transitions to one and only one state. DFA does not allow any
null transitions, meaning every state must have a transition defined for
every input symbol.
DFA consists of 5 tuples {Q, Σ, q, F, δ}.

Q : set of all states.


Σ : set of input symbols. ( Symbols which machine takes as input )
q : Initial state. ( Starting state of a machine )
F : set of final state.
δ : Transition Function, defined as δ : Q X Σ --> Q.

Example:

Construct a DFA that accepts all strings ending with 'a'.

Given:

Σ = {a, b},
Q = {q0, q1},
F = {q1}

Fig 1. State Transition Diagram for DFA with Σ = {a, b}

State\Symbol a b

q0 q1 q0

q1 q1 q0

In this example, if the string ends in 'a', the machine reaches state q1,
which is an accepting state.

2) Non-Deterministic Finite Automata (NFA)

NFA is similar to DFA but includes the following features:


 It can transition to multiple states for the same input.
 It allows null (ϵ) moves, where the machine can change states without
consuming any input.

Example:

Construct an NFA that accepts strings ending in 'a'.

Given:

Σ = {a, b},
Q = {q0, q1},
F = {q1}

Fig 2. State Transition Diagram for NFA with Σ = {a, b}

State Transition Table for above Automaton,

State\Symbol a b

q0 {q0,q1} q0

q1 φ φ

In an NFA, if any transition leads to an accepting state, the string is


accepted.

NFA vs DFA
NFA DFA

Deterministic: exactly one transition Non-deterministic: multiple


per input symbol transitions per input symbol allowed
NFA DFA

No ε (null) moves Allows ε (null) moves

Simpler but sometimes larger in


More flexible and easier to design
design

Next state may be multiple


Next state is uniquely determined
possibilities

Recognizes regular languages; NFAs Recognizes regular languages;


can be converted to DFA equivalent in power to DFA

You might also like