# Study Notes on Finite Automata

By BYJU'S Exam Prep

Updated on: September 25th, 2023

**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.

Table of content

**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_{0}, 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_{0} is initial state and q_{0} ∈ 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:

- The finite automaton M
_{1}has three states, labeled q_{1}, q_{2}, and q_{3}; since these are the labels found in the three circles. Thus, Q = { q_{1}, q_{2}, q_{3}}

**T**he input symbols for M_{1}are 0 and 1, as these are the only labels found on the arrows that represent the transitions. Thus, Σ = { 0, 1 }.

- The start state is q
_{1}, the state shown with an unlabeled input arrow coming from nowhere. - The only state marked with the double circle is q
_{3}, so F = {q_{3}}.

- Transitions:

d(q_{1}, 0 ) = q_{2} d(q_{1}, 1 ) = q_{1}

d(q_{2}, 0 ) = q_{2} d(q_{2}, 1 ) = q_{3}

d(q_{3}, 0 ) = q_{2} d(q_{3}, 1 ) = q_{1}

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

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

*L* = {*x*01*y* | *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_{0}, F), if δ(q_{0}, ω) = F, where q_{0} 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
_{0})

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
_{0}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_{0}), 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**

*Download BYJU’S Exam Prep app for*

**Exam Preparation**here