# Finite Automation Tutorial Notes Study Material with Examples

## Definition** of 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.

**Description of Finite Automaton**

This finite automaton is also known as **Deterministic Finite Automaton** (DFA). But when the transition function maps Q x Ʃ → 2^{Q}, (2^{Q} is called **Powerset function,** is used then that automaton is known as **Non- Deterministic Finite Automaton **(NDFA or NFA).

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

** δ **is transition function which maps Q x Ʃ into Q.

** q _{0 }** is initial state and q

_{0 }ϵ Q.

_{ }**F **is set of final states and f intersection Q.

**Transition Diagrams**

A transition diagram is a finite directed labeled graph in which each vertex represented 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.

e.g., In the given transition diagram, vertex A is the initial state of the finite automata and vertices A and B are the final states and all the edges of this transition diagram are labelled with the inputs.

**Transition Table**

Transition table is the tabular representation of transition system. In this representation, initial (start) state is represented by an arrow towards its and a final state is represented by a circle.

** **

In this transition table, we have mentioned only three states q_{0} , q_{1} and q_{2} , q_{3 }is not mentioned because q_{3} state is not reachable to any other node.

**Key Points**

**Transition function is usually represented by a transition table or a transition diagram.****Finite automata are finite collections of states with transition rules that take input to move from on state to another.****The machine starts in the start state (initial state) and reads in a string of symbols from its alphabet. It uses the transition function δ to determine the next state using the current state and the symbol just read. If, when it has finished reading, it is in an accepting states, it is said to accept the string, otherwise it is said to reject the string.**

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

**Note** :FA (Finite Automata) must accepts those strings which are in the given language but should not accept those strings which are not in the language of finite automata.

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

**Key Points**

**The finite automata has only string pattern recognizing power.****Generally, all FA having only one reading head on the input tape, but a FA having more than one reading head has equal power as FA with one reading head.****A language Lϵ E**^{*}is regular if and only if there is a FA that recognizes L.

**Language of a DFA**

An automata of all kinds defined language. If A is an automata, L(A) is its language.

For a DFA A, L(A) is the set of string labeling paths from the start state to a final state. Formally, L(A) is the set of strings ω such that δ(q_{0}, ω) is in F (final state or set of final states).

e.g. , String 101 is in the language of the DFA below. Start at A. Follow arc labelled 1, then arc labelled 0 from current state B, finally, arc labelled 1 current state A. Result in an accepting state, so 101 is in the language.

The language of our example DFA is:

L = { ω | ω is in {0,1}^{*} and ω does not have two consecutive 1’s}

- Read a set former as the set of strings ω such that these conditions about ω are true.

**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.
- A Deterministic finite automata can simulate the behavior of NFA by increasing the number of states.

**Key Points**

**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 NDFA are DFA.****All NDFA are 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 having ^- moves**

The model NFA include those transitions by which, without giving any input FA can move to the next state.

**Finite Automata With Output Capabilities**

The finite automata was explained in above sections have binary output i.e. , either they accept the string or they do not accept the string.

*Under finite automata, there are two other machines*

**Moore Machine**

It is a finite automata in which output is associated with each state. Each state of Moore Machine has a fix output.

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 δ(Ʃ x Q) → Q.

** q _{0 }** is initial state.

**λ **is output function which maps Q into Δ.

**Mealy Machine**

It is a finite automata in which the output depends upon the present input and present state, both.

Mealy Machine is also a 6-tuples (Q, Ʃ, Δ, δ, λ, q_{0}), Where all symbols except λ have the same meaning as in Moore machine. λ is the output function mapping Ʃ x Q into Δ.

**Key Points**

**We can construct equivalent Mealy machine for a Moore machine and vice-versa.****If M**_{1}and M_{2}respectively, for input string ω. Then, the length of T_{1}(ω) is one greater than the length of T_{2}(ω) i.e. ,

**|T _{1}(ω)|= |T_{1}(ω)| +1**

# A Short Course Compiler Grammar Tutorial Study Notes with Examples

Follow Us on Social Platforms to get Updated : **twiter, ****facebook**

The Complete Guide of Computer Science : Click here

Learn Grammar in Hindi: **Click here **