1
Lahore Garrison University
CSC353-Theory of Automata
Week-4 Lecture-7
Semester-4 Fall 2022
2
Preamble of lecture
► Regular Expressions
Lahore Garrison University
3
Learning Outcomes
► Finite Automata
Lahore Garrison University
4
Finite automaton (FA)
Definition:
► A Finite automaton (FA), is a collection of the followings:
► Finite number of states, having one initial and some (maybe none) final states.
► Finite set of input letters (Σ) from which input strings are formed.
► Finite set of transitions i.e. for each state and for each input letter there is a
transition showing how to move from one state to another.
Lahore Garrison University
5
Finite Automata
► Finite automata are used to recognize patterns.
► It takes the string of symbol as input and changes its state accordingly. When the
desired symbol is found, then the transition occurs.
► At the time of transition, the automata can either move to the next state or stay in the
same state.
► Finite automata have two states, Accept state or Reject state. When the input string is
processed successfully, and the automata reached its final state, then it will accept.
Lahore Garrison University
6
Formal Definition of FA
A finite automaton is a collection of 5-tuple (Q, ∑, δ, q0, F), where:
► Q: finite set of states
► ∑: finite set of the input symbol
► q0: initial state
► F: final state
► δ: Transition function/Movement
►
Lahore Garrison University
7
Example
► Σ = {a,b}
► States: x, y, z where x is an initial state and z is final state.
► Transitions:
► At state x reading a go to state z,
► At state x reading b go to state y,
► At state y reading a, b go to state y
► At state z reading a, b go to state z
Lahore Garrison University
8
Transition Table
► These transitions can be expressed by the following table called transition
table
Old States New States
Reading a Reading b
x- z y
y y y
z+ z z
Lahore Garrison University
9
Note
► It may be noted that the information of an FA, given in the previous table, can also
be depicted by the following diagram, called the transition diagram, of the given
FA
a,b
y
b
a,b
x– a
Z+
Lahore Garrison University
10
Cont..
► The previous transition diagram is an FA accepting the language of strings, defined
over Σ={a, b}, starting with a. It may be noted that this language may be expressed
by the regular expression
a (a + b)*
Lahore Garrison University
11
Cont..
► It may be noted that to indicate the initial state, an arrow head can also be placed before
that state and that the final state with double circle, as shown below. It is also to be
noted that while expressing an FA by its transition diagram, the labels of states are not
necessary.
a, b
a, b
Lahore Garrison University
12
Example
► Σ = {a,b}
States: x, y, where x is both initial and final state.
Transitions:
1. At state x reading a or b go to state y.
2. At state y reading a or b go to state x.
Lahore Garrison University
13
Cont..
► These transitions can be expressed by the following transition
table
Old States New States
Reading Reading
a b
x± y y
y x x
Lahore Garrison University
14
Cont..
► It may be noted that the previous transition table may be depicted by the
following transition diagram.
Lahore Garrison University
15
Cont..
► The previous transition diagram is an FA accepting the language of strings, defined
over Σ={a, b} of even length. It may be noted that this language may be expressed
by the regular expression
((a+ b) (a + b))*
Lahore Garrison University
16
Task
► Build an FA for the language L of strings, defined over Σ={a, b}, of odd length
Lahore Garrison University
17
Solution
a, b
– +
a,b
Lahore Garrison University
18
Example
► Consider the language L of strings, defined over Σ={a, b}, starting with b, may be
accepted by the following FA
Lahore Garrison University
19
Cont..
► The language L may be expressed by RE
b(a + b)*
Lahore Garrison University
20
Example
► Consider the language L of strings, defined over Σ={a, b}, ending in a. This language
may be accepted by the following FA
► There may be another FA corresponding to the given
language.
Lahore Garrison University
21
Cont..
a
a
– +
a b
b
Lahore Garrison University
22
Cont..
The language L may be expressed by
RE (a+b)*a
Lahore Garrison University
23
Note
► It may be noted that corresponding to a given language there may be more than one
FA accepting that language, but for a given FA there is a unique language accepted by
that FA.
Lahore Garrison University
24
Note
► It is to be noted that given the languages L1 and L2 ,where
L1 = The language of strings, defined over Σ={a, b}, beginning with a
L2 = The language of strings, defined over Σ={a, b}, not beginning with b
The Λ does not belong to L1 while it does belong to L2 . This fact may be depicted by the
corresponding transition diagrams of L1 and L2.
Lahore Garrison University
25
FA1 Corresponding to L1
a,b
–
a +
a,b
b
*
► The language L1 may be expressed by the regular expression a(a + b)
Lahore Garrison University
26
FA2 Corresponding to L2
a,b
± a +
b a,b
*
► The language L2 may be expressed by the regular expression a (a + b) + Λ
Lahore Garrison University
27
Example
► Consider the Language L of Strings of length two or more, defined over Σ = {a, b},
beginning with and ending in same letters.
b a a
+
a b
–
a b
b
b
+
a
Lahore Garrison University
28
Cont..
The language L may be expressed by the following regular
expression a (a + b)* a + b (a + b)* b
Lahore Garrison University
29
Cont..
► It is to be noted that if the condition on the length of string is not imposed in the
above language then the strings a and b will then belong to the language
Lahore Garrison University
30
Task
► Build an FA accepting the Language L of Strings, defined over Σ = {a, b}, beginning
with and ending in same letters
Lahore Garrison University
31
Q&A
Lahore Garrison University
32
References
Lahore Garrison University
