Chapter One

Introduction
Automata and Complexity Theory
Outline

• Chapter 1: Introduction
1.1. Alphabets and strings
1.2. Languages and Grammars
1.3. Automata
1.3.1. Finite automata [ Deterministic
and Non-deterministic ]
Introduction
• Automata and Complexity Theory is all about
understanding the fundamental capabilities and
limitations of computers.
• It helps us figure out what problems computers can solve,
and
• How efficiently they can solve them.
• Think of it like this:
• Automata Theory is about building abstract machines
that can perform computations, while
• Complexity Theory is about measuring how much "work"
those computations require.
Cont …
• Foundations of Automata Theory -
Alphabets, Strings, Languages, and
Grammars.
• We're going to start at the very beginning,
with the most fundamental components of
computation.
• These might seem simple at first glance, but
they are the bedrock upon which all more
complex ideas in automata theory are built.
1.1. Alphabets and Strings
Alphabet Σ(Sigma)
• An alphabet, denoted by Σ (Sigma), is a
finite, non-empty set of symbols.
• These symbols are the atomic units we use
to construct information.
• Think of them as the letters in a natural
language.
Example

Binary Alphabet English Alphabet

• The most common alphabet • Σ = {a, b, c, ..., z}
in computer science is the • We could even consider an
binary alphabet:
alphabet of just specific
• Σ = {0, 1} letters, like:
• This is the language of • Σ = {a, b, c}
computers – everything
ultimately boils down to
sequences of 0s and 1s.
Cont …

Set of Digits Special Characters

• Σ = {0, 1, 2, 3, 4, 5, 6, 7, • Σ = {+, -, *, /, =}
8, 9} • An alphabet for basic
• This alphabet is used to arithmetic operations.
form numbers.
• The alphabet
• must be finite.
• We can't have an infinite number of distinct symbols.
• And it must be non-empty;
• we need at least one symbol to do anything!
String (or Word)
• A string (or sometimes called a word) over an alphabet
Σ is a finite sequence of symbols from Σ.
• Binary Alphabet Σ= {0, 1}: • Alphabet Σ= {a, b, c}:
• 0101 • abca
• 111000
• ccba
• 0
•B
• 1
• The empty string is also a valid
• Empty String
string.
• It's a string with zero symbols.
• It's crucial for many theoretical
constructions.
Properties of Strings
• Length of a String
• It is often useful to classify strings by their
length, that is, the number of positions for
symbols in the string.
• For instance: 01101 has length 5.
• It is common to say that the length of a string
is “the number of symbols” in the string.
• The standard notation for the length of a string
w is |w|.
• For example: |011|=3 and |ε|=0
Cont …
• Concatenation:
• If x and y are strings, then xy is their
concatenation. This means joining x and y end-to-
end.
• If x = ab and y = ca, then xy = abca.
• If x = 01 and y = 11, then xy = 0111.
• Note that string concatenation is not
commutative: xy ≠ yx in general.
• The empty string ε (epsilon) acts as an identity
for concatenation: we = ew = w for any string w .
Cont …
• Powers of a String:
• w^k means string w concatenated with
itself k times.
• If w = ab, then w^2 = abab, w^3 = ababab.
• w^0 = ε (epsilon) (any string raised to the
power of 0 is the empty string).
Cont …
• Important Notation:
• Σ* (Sigma Star): This denotes the set of all
possible strings over an alphabet Σ, including the
empty string ε(epsilon).
• This set is infinite if Σ is not empty.
• If Σ = {0, 1}, then Σ * = {ε, 0, 1, 00, 01, 10, 11, 000, ...}
• + (Sigma Plus): This denotes the set of all
possible non-empty strings over an alphabet Σ.
• Σ+ = Σ* - {ε}
1.2. Languages &
Grammars
Language
• Now that we have words, how do we define
meaningful collections of these words?
• That brings us to languages.
• A language L over an alphabet Σ is any subset of Σ*.
• In other words, a language is a collection of strings,
where each string is composed of symbols from Σ.
• A language is a set of strings formed from an
alphabet. Formally, a language is any subset of Σ*.
Cont …
• A language may be:
• Finite: Only a finite number of strings
(e.g., L = {a, aa, aaa})
• Infinite: Unlimited strings (e.g., L = {aⁿ |
n ≥ 0})
• Empty: ∅
• Universal: All possible strings over Σ
(i.e., Σ*)
Cont …
• Examples:
• L1 = {aⁿ | n ≥ 0} = {ε, a, aa, aaa, ...}
• L2 = {w ∈ {0,1}* | w contains an even number of 0s}
• L3 = {w | w is a palindrome over Σ = {a, b}} (e.g., ε, "a", "aba",
"abba")
• Operations on Languages
• Union (L₁ ∪ L₂): L₁ = {a, aa}, L₂ = {b, bb} → L₁ ∪ L₂ = {a, aa, b,
bb}
• Concatenation (L₁·L₂): L₁ = {a, ab}, L₂ = {b, ba} → L₁·L₂ = {ab,
aba, abb, abba}
• Kleene Star (L*): L = {a, b} → L* = {ε, a, b, aa, ab, ba, bb, aaa,
...}
Grammar
• While a language is a set of strings, a
grammar provides:
• A formal mechanism or
• a set of rules for generating precisely those
strings that belong to a particular language.
• Think of it as the blueprint or recipe for
creating valid "sentences" in a language.
1.1.3. Automata
Automata
• Finite automata are abstract machines used to
recognize patterns in input sequences, forming
the basis for understanding regular languages in
computer science.
• They consist of states, transitions, and input
symbols, processing each symbol step-by-step.
• If the machine ends in an accepting state after
processing the input, it is accepted;
• otherwise, it is rejected.
Cont …
• An automaton: is a mathematical model
of computation that:
• Reads an input string (one symbol at a
time).
• Changes its state based on transitions.
• Accepts or rejects the input based on
final states.
Cont …
• Finite automata come in:
• deterministic (DFA) and
• non-deterministic (NFA),
• both of which can recognize
the same set of regular
languages.
• They are widely used in text
processing, compilers, and
network protocols.
Features of Finite Automata
• Input: Set of symbols or characters provided to
the machine.
• Output: Accept or reject based on the input
pattern.
• States of Automata: The conditions or
configurations of the machine.
• State Relation: The transitions between states.
• Output Relation: Based on the final state, the
output decision is made.
Formal Definition of Finite
Automata
• A finite automaton can be defined as a tuple: { Q,
Σ, q, F, δ }, where:
• Q: Finite set of states
• Σ: Set of input symbols
• q: Initial state
• F: Set of final states
• δ: Transition function
Types of Finite Automata
• There are two types of finite automata:
1. Deterministic Fintie Automata (DFA)
2. Non-Deterministic Finite Automata (NFA)
1.3.1. Finite automata
Deterministic
Non-deterministic
Deterministic Finite Automata
(DFA)
• A DFA is represented as {Q, Σ, q, F, δ}.
• In DFA, for each input symbol, the machine
transitions to one and only one state.
• DFA does not allow any null transitions,
meaning every state must have a transition
defined for every input symbol.
Cont …
• DFA consists of 5 tuples {Q, Σ, q, F, δ}.
• Q : set of all states.
• Σ : set of input symbols. ( Symbols which
machine takes as input )
• q : Initial state. ( Starting state of a machine )
• F : set of final state.
• δ : Transition Function, defined as δ : Q X Σ -->
Q.
Example:
• Construct a DFA that accepts
all strings ending with 'a’.
• Given:
• Σ = {a, b},
• Q = {q0, q1},
• F = {q1}
State \Symbol
a b
• In this example, if the string
ends in 'a', the machine reaches q0 q1 q0
state q1, which is an accepting
q1 q1 q0
state.
 Cont …
Input
• Key Takeaways
Final
Strin Path
State
Accept/Reject 1. DFA must remember the last
g symbol seen.
a. If it's 'a', go to q₁.
"a" q₀ → q₁ q₁ ✅ Accept b. If it's 'b', stay in q₀.
"ba" q₀ → q₁ q₁ ✅ Accept 2. Only q₁ is accepting because it
means the string ends with 'a'.
"bb" q₀ → q₀ q₀ ❌ Reject
3. Every input symbol updates
the state based on the last
"abaa
q₀ → q₁ →
q₀ → q₁ → q₁ ✅ Accept
character.
"
q₁
Non-Deterministic Finite Automata
(NFA)
• NFA is similar to DFA but includes the following
features:
• It can transition to multiple states for the same
input.
• It allows null (ϵ) moves, where the machine
can change states without consuming any
input.
Example:
• Construct an NFA that
accepts strings ending in
'a'.
• Given:
• Σ = {a, b},
• Q = {q0, q1},
• F = {q1} State \Symbol
a b
q0 {q0,q1} q0
• In an NFA, if any transition
leads to an accepting q1 φ φ
state, the string is
accepted.
Comparison of DFA and NFA
• Although NFAs appear more flexible, they do not
have more computational power than DFAs.
Every NFA can be converted to an equivalent
DFA, although the resulting DFA may have more
states.
• DFA: Single transition for each input symbol, no null
moves.
• NFA: Multiple transitions and null moves allowed.
• Power: Both DFA and NFA recognize the same set of
regular languages.
Conclusion
• Finite automata, whether deterministic or non-
deterministic, are powerful tools in pattern recognition
and regular language processing.
• They form the backbone of many computational
processes, especially in text analysis and compiler
design.
• While DFAs are simpler and more commonly used, NFAs
offer a more flexible yet equivalent way to define
regular languages.
• Understanding the nuances of both helps in optimizing
various algorithms in computer science.
Excersice
• Construct a DFA • Design an NFA that
accepting strings accepts strings over
over {x, y} with at {0, 1} with an even
least one 'x’. number of '0's or an
• Given: odd number of '1’s.
• Alphabet: {x, y} • Given:
• Condition: Must • Alphabet: {0, 1}
contain at least one • Condition: Even '0's
'x'. or odd '1's.
End of Chapter One
Instructor – Biniyam Efrem