Short Notes: Regular Expressions & Finite Automata | Short Notes for Computer Science Engineering - Computer Science Engineering (CSE) PDF Download

 Page 1


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.
Input
values
Finite 
automaton 
having n 
states 
(Qi « J 2 Qn)
Output
values
Model ol finite automaton
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, I, 5, qo, F). where, Q is finite non-empty 
set of states, I is finite non-empty set of input d alphabets, 5 is transition function 
which maps Q x I into Q, qo is initial state and qo e Q, F is set of final states and F 
c Q .
• For DFA: Q x I — ? Q
• For NFA: Q x I — ? 2°
. For epsilon-NFA: Q x I u {epsilon}-* 2°
Transition Diagrams
Page 2


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.
Input
values
Finite 
automaton 
having n 
states 
(Qi « J 2 Qn)
Output
values
Model ol finite automaton
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, I, 5, qo, F). where, Q is finite non-empty 
set of states, I is finite non-empty set of input d alphabets, 5 is transition function 
which maps Q x I into Q, qo is initial state and qo e Q, F is set of final states and F 
c Q .
• For DFA: Q x I — ? Q
• For NFA: Q x I — ? 2°
. For epsilon-NFA: Q x I u {epsilon}-* 2°
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
1
Important observations for the above FA:
1. The finite automaton Mi has three states, labeled qi, q2, and q3; since 
these are the labels found in the three circles. Thus, Q = { qi, q2, q3 }
2. The input symbols for Mi are 0 and 1, as these are the only labels found on 
the arrows that represent the transitions. Thus, I = { 0,1 }.
3. The start state is qi, the state shown with an unlabeled input arrow coming 
from nowhere.
4. The only state marked with the double circle is q3, so F = {q3}.
5. Transitions:
d (q i,0 ) = q2 d(qi, 1 ) = qi
d(q2 . 0 ) = q2 d(q2, 1 ) = q3
d(q3, 0 ) = q2 d(q3, 1 ) = qi
6. FA accepts all strings where each string ends with 01.
Problem-1: Construct DFA that accepts the language L given below.
L = {xOly | 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:
Transition table is the tabular representation of transition system.
In this representation, initial (start) state is represented by an arrow towards it and 
a final state is represented by a circle or prefixed with star symbol.
Following transition table is equivalent to the above given transition diagram.
Page 3


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.
Input
values
Finite 
automaton 
having n 
states 
(Qi « J 2 Qn)
Output
values
Model ol finite automaton
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, I, 5, qo, F). where, Q is finite non-empty 
set of states, I is finite non-empty set of input d alphabets, 5 is transition function 
which maps Q x I into Q, qo is initial state and qo e Q, F is set of final states and F 
c Q .
• For DFA: Q x I — ? Q
• For NFA: Q x I — ? 2°
. For epsilon-NFA: Q x I u {epsilon}-* 2°
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
1
Important observations for the above FA:
1. The finite automaton Mi has three states, labeled qi, q2, and q3; since 
these are the labels found in the three circles. Thus, Q = { qi, q2, q3 }
2. The input symbols for Mi are 0 and 1, as these are the only labels found on 
the arrows that represent the transitions. Thus, I = { 0,1 }.
3. The start state is qi, the state shown with an unlabeled input arrow coming 
from nowhere.
4. The only state marked with the double circle is q3, so F = {q3}.
5. Transitions:
d (q i,0 ) = q2 d(qi, 1 ) = qi
d(q2 . 0 ) = q2 d(q2, 1 ) = q3
d(q3, 0 ) = q2 d(q3, 1 ) = qi
6. FA accepts all strings where each string ends with 01.
Problem-1: Construct DFA that accepts the language L given below.
L = {xOly | 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:
Transition table is the tabular representation of transition system.
In this representation, initial (start) state is represented by an arrow towards it and 
a final state is represented by a circle or prefixed with star symbol.
Following transition table is equivalent to the above given transition diagram.
0 1
*2 %
%
*1
$2 *2 *1
(— »: initial state; *: final state)
Acceptability of a String by Finite Automata
A string ut is accepted by a finite automaton, M = (Q, Z, 5, q0, F), if 5(q0, w) = F , 
where q0 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. 5(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.
5*(q, cj) = 5(5(q, x), a)
where, w is a string i.e., u) = 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 e-transition (null transition).
• For every (q, a) with q e Q and a e Z 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 Autom ata 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, Z, A, 5, A , q0)
where, Q is finite non-empty set of states.
Page 4


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.
Input
values
Finite 
automaton 
having n 
states 
(Qi « J 2 Qn)
Output
values
Model ol finite automaton
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, I, 5, qo, F). where, Q is finite non-empty 
set of states, I is finite non-empty set of input d alphabets, 5 is transition function 
which maps Q x I into Q, qo is initial state and qo e Q, F is set of final states and F 
c Q .
• For DFA: Q x I — ? Q
• For NFA: Q x I — ? 2°
. For epsilon-NFA: Q x I u {epsilon}-* 2°
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
1
Important observations for the above FA:
1. The finite automaton Mi has three states, labeled qi, q2, and q3; since 
these are the labels found in the three circles. Thus, Q = { qi, q2, q3 }
2. The input symbols for Mi are 0 and 1, as these are the only labels found on 
the arrows that represent the transitions. Thus, I = { 0,1 }.
3. The start state is qi, the state shown with an unlabeled input arrow coming 
from nowhere.
4. The only state marked with the double circle is q3, so F = {q3}.
5. Transitions:
d (q i,0 ) = q2 d(qi, 1 ) = qi
d(q2 . 0 ) = q2 d(q2, 1 ) = q3
d(q3, 0 ) = q2 d(q3, 1 ) = qi
6. FA accepts all strings where each string ends with 01.
Problem-1: Construct DFA that accepts the language L given below.
L = {xOly | 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:
Transition table is the tabular representation of transition system.
In this representation, initial (start) state is represented by an arrow towards it and 
a final state is represented by a circle or prefixed with star symbol.
Following transition table is equivalent to the above given transition diagram.
0 1
*2 %
%
*1
$2 *2 *1
(— »: initial state; *: final state)
Acceptability of a String by Finite Automata
A string ut is accepted by a finite automaton, M = (Q, Z, 5, q0, F), if 5(q0, w) = F , 
where q0 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. 5(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.
5*(q, cj) = 5(5(q, x), a)
where, w is a string i.e., u) = 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 e-transition (null transition).
• For every (q, a) with q e Q and a e Z 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 Autom ata 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, Z, A, 5, A , q0)
where, Q is finite non-empty set of states.
• I is set of input symbols.
• A is output alphabet.
• 5 is transition function which maps 5(1 * Q) -» Q.
• A is output function which maps Q into A.
• q0 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, Z, A, 5, A , q0), where all symbols 
except A have the same meaning as in Moore machine. A is the output function 
mapping Z x Q into A.
Sequence detector 11011 using Mealy machine:
Regular Expression
Regular expressions mean to represent certain sets of strings in some algebraic 
fashion. A regular expression over the alphabet Z is defined as follows
• 4 > is a regular expression corresponding to the empty language
• e is a regular expression corresponding to the language { e}.
• For each symbol a eZ a is a regular expression corresponding to the language 
{a}.
Regular Language
The languages accepted by FA are regular languages and these languages are 
easily described by simple expressions called regular expressions.
For any regular expression r and s over Z corresponding to the languages Lr and Ls 
respectively, each of the following is a regular expression corresponding to the 
language indicated.
• (rs) corresponding to the language LrLs
• (r + s) corresponding to the language Lr u Ls
• r* corresponding to the language Lr. Some examples of regular expression are
1. L (01) = {0,1}
2. L (01 + 0) = {01,0}
3. L (0 (1+0)) = {01, 00}
4. L (0*) = {e, 0, 00, 000,...}
5. L ((0 + 10)* (e + 1)) = all strings of 0's and 1's without two consecutive 
1 s.
Page 5


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.
Input
values
Finite 
automaton 
having n 
states 
(Qi « J 2 Qn)
Output
values
Model ol finite automaton
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, I, 5, qo, F). where, Q is finite non-empty 
set of states, I is finite non-empty set of input d alphabets, 5 is transition function 
which maps Q x I into Q, qo is initial state and qo e Q, F is set of final states and F 
c Q .
• For DFA: Q x I — ? Q
• For NFA: Q x I — ? 2°
. For epsilon-NFA: Q x I u {epsilon}-* 2°
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
1
Important observations for the above FA:
1. The finite automaton Mi has three states, labeled qi, q2, and q3; since 
these are the labels found in the three circles. Thus, Q = { qi, q2, q3 }
2. The input symbols for Mi are 0 and 1, as these are the only labels found on 
the arrows that represent the transitions. Thus, I = { 0,1 }.
3. The start state is qi, the state shown with an unlabeled input arrow coming 
from nowhere.
4. The only state marked with the double circle is q3, so F = {q3}.
5. Transitions:
d (q i,0 ) = q2 d(qi, 1 ) = qi
d(q2 . 0 ) = q2 d(q2, 1 ) = q3
d(q3, 0 ) = q2 d(q3, 1 ) = qi
6. FA accepts all strings where each string ends with 01.
Problem-1: Construct DFA that accepts the language L given below.
L = {xOly | 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:
Transition table is the tabular representation of transition system.
In this representation, initial (start) state is represented by an arrow towards it and 
a final state is represented by a circle or prefixed with star symbol.
Following transition table is equivalent to the above given transition diagram.
0 1
*2 %
%
*1
$2 *2 *1
(— »: initial state; *: final state)
Acceptability of a String by Finite Automata
A string ut is accepted by a finite automaton, M = (Q, Z, 5, q0, F), if 5(q0, w) = F , 
where q0 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. 5(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.
5*(q, cj) = 5(5(q, x), a)
where, w is a string i.e., u) = 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 e-transition (null transition).
• For every (q, a) with q e Q and a e Z 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 Autom ata 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, Z, A, 5, A , q0)
where, Q is finite non-empty set of states.
• I is set of input symbols.
• A is output alphabet.
• 5 is transition function which maps 5(1 * Q) -» Q.
• A is output function which maps Q into A.
• q0 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, Z, A, 5, A , q0), where all symbols 
except A have the same meaning as in Moore machine. A is the output function 
mapping Z x Q into A.
Sequence detector 11011 using Mealy machine:
Regular Expression
Regular expressions mean to represent certain sets of strings in some algebraic 
fashion. A regular expression over the alphabet Z is defined as follows
• 4 > is a regular expression corresponding to the empty language
• e is a regular expression corresponding to the language { e}.
• For each symbol a eZ a is a regular expression corresponding to the language 
{a}.
Regular Language
The languages accepted by FA are regular languages and these languages are 
easily described by simple expressions called regular expressions.
For any regular expression r and s over Z corresponding to the languages Lr and Ls 
respectively, each of the following is a regular expression corresponding to the 
language indicated.
• (rs) corresponding to the language LrLs
• (r + s) corresponding to the language Lr u Ls
• r* corresponding to the language Lr. Some examples of regular expression are
1. L (01) = {0,1}
2. L (01 + 0) = {01,0}
3. L (0 (1+0)) = {01, 00}
4. L (0*) = {e, 0, 00, 000,...}
5. L ((0 + 10)* (e + 1)) = all strings of 0's and 1's without two consecutive 
1 s.
• If Li and L2 are regular languages in I*, then Li u L2, Li fl L2, Li - L2 and L 
(complement of Li), are all regular languages.
• Pumping lemma is a useful tool to prove that a certain language is not 
regular.
Regular Set
A set represented by a regular expression is called regular set e.g., If Z = {a, b} is an 
alphabet, then
Different Regular Sets and their Expressions
S e ts R e g u la r E x p r e s s io n
{ ) < t>
{a ) a
{ a : b } a - b
{ e, a, aa, a a a ,...} a*
{a , aa, a a a ,...} aa* = a+
Identities for Regular Expressions
The following points are the some identities for regular expressions.
• 4 > + R = R + 4 > = R
• £ R = R £ = R
• R + R = R, where R is the regular expression.
• (R*)* = R* 4 > R = R c |> = 4 >
• £ * = £ and c > * = e
• RR* = R*R = R+
• R*R* = R*
• (P + Q)* = (P*Q*)* = (P* + Q*)*, where P and Q are regular expressions.
• R (P + Q) = RP + RQ and (P + Q)R = PR + QR
• P(QP)* = (PQ)*P
Arden’s Theorem
• If P and Q are two expressions over an alphabet Z such that P does not 
contain e, then the following equation R = Q + RP.
• The above equation has a unique solution i.e., R = QP*. Arden's theorem is 
used to determine the regular expression represented by a transition diagram.
• The following points are assumed regarding transition diagrams
• The transition system does not have any
• It has only one initial (starting) stage.
Properties of Regular Language
Regular languages are closed under following opearations
1. Union
2. Concatenation
3. Kleene closure
4. Complementation
5. Transpose
6. Intersection