Study Notes on Finite Automata

Finite Automaton

A Finite State Machine (FSM) or finite-state automaton is an abstract machine used in the study of computation and language that has only a finite, constant amount of memory.

Types of Finite Automaton:

• Deterministic Finite Automata (DFA)
• Non-Deterministic Finite Automata (NFA or NDFA)
• NFA with Epsilon moves (epsilon-NFA)

Description of Finite Automaton

A finite automaton is defined as 5-tuples (Q, Σ, δ, q₀, F). where, Q is finite non-empty set of states, Σ is finite non-empty set of input d alphabets, δ is transition function which maps Q × Σ into Q, q₀ is initial state and q₀ ∈ Q, F is set of final states and F ⊆ Q.

• For DFA: Q × Σ → Q
• For NFA: Q × Σ → 2^Q
• ^{For epsilon-NFA : Q × Σ U {epsilon}→ 2Q}

Transition Diagrams

A transition diagram is a finite directed labelled graph in which each vertex represents a state and directed edges indicate the transition from one state to another. Edges are labelled with input/output. In this, the initial state is represented by a circle with an arrow towards it, the final state is represented by two concentric circles and intermediate states are represented by just a circle.

Example: Consider the following Finite Automata

Important observations for the above FA:

1. The finite automaton M₁ has three states, labeled q₁, q₂, and q₃; since these are the labels found in the three circles.  Thus, Q = { q₁, q₂, q₃ }

2. The input symbols for M₁ are 0 and 1, as these are the only labels found on the arrows that represent the transitions.  Thus,  Σ = { 0, 1 }.

3. The start state is q₁, the state shown with an unlabeled input arrow coming from nowhere. 
4. The only state marked with the double circle is q₃, so F = {q₃}.

5. Transitions:

            d(q₁, 0 ) = q₂              d(q₁, 1 ) = q₁
            d(q₂, 0 ) = q₂              d(q₂, 1 ) = q₃
            d(q₃, 0 ) = q₂              d(q₃, 1 ) = q₁

6. FA accepts all strings where each string ends with 01.

Problem-1: Construct DFA that accepts the language L given below.

L = {x01y | x and y are any strings of 0’s and 1’s}.

DFA for above L:

 

In the given transition diagram, vertex A is the initial state of the finite automata and C is the final state.

Transition Table:

The transition table is the tabular representation of the transition system.

In this representation, the initial (start) state is represented by an arrow towards it and a final state is represented by a circle or prefixed with a star symbol.

Following the transition, the table is equivalent to the above-given transition diagram.

Acceptability of a String by Finite Automata

A string ω is accepted by a finite automaton, M = (Q, Σ, δ, q₀, F), if δ(q₀, ω) = F, where q₀ is initial (start) state and F is the final state. For every input symbol of string it takes one transition and starts with initial state and reaches final state by reading the complete string.

Transition Function

It takes two arguments i.e., a state and an input symbol. δ(q, a) is the transition function for the DFA (Deterministic Finite Automata) which is at the state q and when it receives the input a, DFA will move to the next state.

Extended Transition Function

It takes two arguments a state and an input string.

δ^*(q, ω) = δ(δ(q, x), a)

where, ω is a string i.e., ω = xa, in which a is a single word and x is remaining string except the last symbol.

Equivalence of DFA and NDFA

In contrast to the NFA (NDFA), the Deterministic Finite Automata (DFA) has

• No ε-transition (null transition).
• For every (q, a) with q ∈ Q and a ∈ Σ at most one successor state.
• Deterministic finite automata can simulate the behaviour of NFA by increasing the number of states.
• In Deterministic Finite Automata (DFA), for each state, there is at most one transition for each possible input.
• In non-deterministic finite automata, there can be more than one transition from a given state for a given possible input.
• If a language L is accepted by an NFA, then there is a DFA that accepts L.
• All DFA are NDFA, but not all NFA are DFA.
• All NDFA and DFA have the same power.
• Processing of an input string is more time consuming when NFA is used and less time consuming when DFA is used.

Finite Automata with Output Capabilities

There are two types of machines: Moore machine and Mealy machine.

Moore Machine

• It is a finite automata in which output is associated with each state.
• Moore machine is defined as 6-tuples (Q, Σ, Δ, δ, λ, q₀)

where, Q is finite non-empty set of states.

• Σ is set of input symbols.
• Δ is output alphabet.
• δ is transition function which maps δ(Σ × Q) → Q.
• λ is output function which maps Q into Δ.
• q₀ is initial state.

Mealy Machine

It is a finite automata in which the output depends upon both the present input and present state. Mealy machine is also a 6-tuple (Q, Σ, Δ, δ, λ, q₀), where all symbols except λ have the same meaning as in Moore machine. λ is the output function mapping Σ × Q into Δ.

Sequence detector 11011 using Mealy machine:

 

You can follow the detailed champion study plan for GATE CS 2021 from the following link:

Detailed GATE CSE 2021 Champion Study Plan

Candidates can also practice 110+ Mock tests for exams like GATE, NIELIT with BYJU’S Exam Prep Test Series check the following link:

Click Here to Avail GATE CSE Test Series!(100+ Mock Tests)

Get unlimited access to 21+ structured Live Courses all 112+ mock tests with Online Classroom Program for GATE CS & PSU Exams:

Click here to avail Online Classroom Program for Computer Science Engineering

Thanks

#DreamStriveSucceed