Finite Automata Theory, Computational Theory Basics

Finite Automata Theory

1. MODULE 1
THEORY OF COMPUTATION

3. THEORY OF COMPUTATION
☻The Theory of Computation is a branch of computer science and
mathematics.
☻It focuses on understanding the capabilities and limitations of
computing machines.
☻ It provides a mathematical framework to analyze what problems can
be solved by a computer and how efficiently they can be solved.
☻The theory of computation includes the fundamental mathematical
properties of computer hardware, software and their applications.
3

4. The theory of computation field is divided into three concepts.
Automated theory and language.
Computability theory.
Complexity theory.
4

5. 5

6. 6

7. 7

8. 8
Automata –
The term "Automata" is derived from the Greek word "α τόματα"
ὐ
which means "self-acting".
 An automaton (Automata in plural) is an abstract self-propelled
computing device which follows a predetermined sequence of
operations automatically.
An automaton with a finite number of states is called a
 
Finite
Automaton 
(FA) or 
Finite State Machine 
(FSM).

10. SYMBOL( CHARACTER)
A single element of an alphabet.
In the alphabet Σ = {a, b, c}, the symbols are a, b, and c.

11. ALPHABET (Σ)
•A finite, non-empty set of symbols used to construct strings.
∑ = {a, b, c, d} is an
 
alphabet set 
where ‘a’, ‘b’, ‘c’, and ‘d’
are
 
symbols.
For binary, the alphabet is: Σ = {0, 1}
For English, it might be: Σ = {a, b, c, ..., z}

12. STRING
A finite sequence of symbols from an alphabet.
Example:
•For Σ = {0, 1}, possible strings are: 0, 1, 01, 110, etc.
Special Strings:
•Empty String (ε): A string with no symbols. Its length is 0.
ε is an empty string.
•Length of a String: The number of symbols in a string.
For the string "101", the length is 3.
For alphabet {a, b} with length n, number of strings can be generated = 2
n

13. LANGUAGE (L)
A set of strings formed from an alphabet.
For Σ = {a, b}, a language could be: L = {a, ab, bba}.
Types of Languages:
•Finite Language: Contains a finite number of strings.
Example: L = {ε, a, aa}.
•Infinite Language: Contains an infinite number of
strings.
Example: L = {a, aa, aaa, aaaa, ...}.

14. Operations on Strings
a) Concatenation
Joining two strings end-to-end.
If x = "ab" and y = "c", then xy = "abc".
b) Reversal
Reversing the order of symbols in a string.
Example: For x = "abc", the reversal is "cba".
c) Length
•Represented as |x|, where x is a string.
|abc| = 3.
d) Power
Repeating a string multiple times
x² = xx = "ab" + "ab" = "abab".
x = ε.
⁰

15. Language Operations
a) Union (L L )
₁ ∪ ₂
Combines all strings from both languages.
Example: If L = {a, b} and L = {b, c}, then L L = {a, b, c}
₁ ₂ ₁ ∪ ₂
b) Intersection (L ∩ L )
₁ ₂
Common strings in both languages.
Example: If L = {a, b} and L = {b, c}, then L ∩ L = {b}
₁ ₂ ₁ ₂
c) Concatenation (L L )
₁ ₂
Combines strings by appending one after the other.
Example: If L = {a, b} and L = {c}, then L L = {ac, bc}
₁ ₂ ₁ ₂
d) Kleene Star (L)*
Represents the set of all possible concatenations of strings,
including the empty string (ε).
Example: If L = {a}, then *L = {ε, a, aa, aaa, ...}**

16. CLOSURE REPRESENTATION IN TOC
L+: It is a Positive Closure that represents a set of all strings
except Null or ε-strings.
The Kleene star (denoted as L* for a language L) represents
the set of all possible strings that can be formed by
concatenating zero or more strings from L (including the
empty string ε).
Mathematically:
??????∗={ } 2 3 …
?????? ∪??????∪?????? ∪?????? ∪
L
∗
={ } L L 2 L 3 …where Lⁿ represents the set of all strings
ϵ ∪ ∪ ∪ ∪
formed by concatenating n strings from L.

17. CLOSURE REPRESENTATION IN TOC
L*: It is “Kleene Closure“, that represents the occurrence of
certain alphabets for given language alphabets from zero to
the infinite number of times. In which ε-string is also included.
From the above two statements, it can be concluded that:
L* = εL+

18. CLOSURE REPRESENTATION IN TOC
Positive Closure (L )
⁺
The set of all strings that can be formed by concatenating one or
more strings from the language L.
??????
Unlike Kleene closure, it does not include the empty string (
??????
ε).
??????+= 2 3 …L + =L L 2 L 3 …where:
??????∪?????? ∪?????? ∪ ∪ ∪ ∪
??????1= L 1 =L 2={ , }L 2 ={xyx,y L}, and so on.
?????? ?????? ????????????∣?????? ??????∈?????? ∣ ∈
If ={ , }L={a,b}, then: +={ , , , , , , , ,...}
?????? ?????? ?????? ?????? ?????? ?????? ???????????? ???????????? ???????????? ?????????????????????????????? ??????????????????
L + ={a,b,aa,ab,ba,bb,aaa,aab,...}

19. A language is a subset of ∑* for some alphabet ∑. It can be finite or
infinite.
•Example 
− If the language takes all possible strings of length 2 over ∑ =
{a, b}, then L = { ab, aa, ba, bb }
19

20. DFA (Deterministic finite automata)
•DFA refers to deterministic finite automata.
•Deterministic refers to the uniqueness of the computation. The finite automata
are called deterministic finite automata if the machine reads an input string
one symbol at a time.
•In DFA, there is only one path for specific input from the current state to the
next state.
•DFA does not accept the null move, i.e., the DFA cannot change state without
any input character.
•DFA can contain multiple final states. It is used in Lexical Analysis in
Compiler.
20

21. In this diagram, we can see that from state q0 for
input a, there is only one path which is going to q1.
Similarly, from q0, there is only one path for input b
going to q2.
The state is represented by
vertices.
The arc labeled with an
input character show the
transitions.
The initial state is marked
with an arrow.
The final state is denoted by
a double circle.

22. •Formal Definition of an NDFA
•An NDFA can be represented by a 5-tuple (Q, ∑, δ, q
0, F) where −
•Q is a finite set of states.
•∑ is a finite set of symbols called the alphabets.
•δ is the transition function where δ: Q × ∑ → 2
Q
(Here the power set of Q (2
Q
) has been taken because in case of NDFA, from
a state, transition can occur to any combination of Q states)
•q
0
 is the initial state from where any input is processed (q
0
  Q).
∈
•F is a set of final state/states of Q (F Q).
⊆
22

23. •The vertices represent the states.
•The arcs labeled with an input alphabet show the transitions.
•The initial state is denoted by an empty single incoming arc.
•The final state is indicated by double circles.
Let a non-deterministic finite automaton be
•Q = {a, b, c}
•∑ = {0, 1}
•q
0 
= {a}
•F = {c}
23
Present State
Next State for
Input 0
Next State for
Input 1
a a, b b
b c a, c
c b, c c
The transition function δ as shown below −

25. Let a deterministic finite automaton be
•Q = {a, b, c}
•∑ = {0, 1}
•q
0 
= {a}
•F = {c}
25
Present
State
Next State
for Input 0
Next State
for Input 1
a a b
b c a
c b c
Transition function δ as shown by the following table −

26. Example 1:
Q = {q0, q1, q2}
∑ = {0, 1}
q0 = {q0}
F = {q2}
Present StateNext state for
Input 0
Next State of
Input 1
→q0 q0 q1
q1 q2 q1
*q2 q2 q2