Automata Theory

Lecture 01 and 02
Thursday, JULY
18th 2024

1
 Course Introduction
• Course C.Hs:
• 04 C.Hs:
- Theoretical work
- Practical work
• Recommended Text Books:
• Introduction to Automata Theory, Languages and Computation
J.E. Hopcroft, R. Motwani, J.D. Ullman
3rd Edition (Addison Wesley/Pearson)
• Introduction to the Theory of Computation, 2nd Ed.
Michael Sipser
• Introduction to Computer Theory
Daniel I.A. Cohen
• Theory of Automata, Formal Languages and Computation
S. P. Eugene Xavier
• Online Literature
 Course Introduction
• Teaching plan:

• 02 tests:
- At the end of 20th and 45th lectures respectively

• Class exercises

• Short presentations

• Practical exercises
 During the Course

• During the lecture:

• Be punctual/regular

• Concentrate on the lecture

• Remain active and interactive

• Try to find/ask (research) questions

• Think in terms of “why”, “how”

 What to Seek?

• In studying this subject, seek to determine:

• What can and cannot be computed ?

• How quickly ?

• With how much memory ? and

• On which type of computational model ?

 Course Outline
• Introduction
• Regular Languages and their descriptors
- Finite state automata
- Non-deterministic automata
- Regular expressions
- Algorithms to decide questions about regular languages,
e.g., is it empty?
- Closure properties of regular languages.
• Context Free Languages and their descriptors
- Context free grammars
- Pushdown automata
• Turing Machines and TM Variants
• Decidable and Undecidable Languages
• Time and Space Complexities
 Lecture Outline

• Introduction
• Models of Computation
• Languages
 What is Automata Theory?
• Study of abstract computing devices, or “machines”

• Automaton = an abstract computing device

Note: A “device” need not even be a physical hardware!

• A fundamental question in computer science:

▪ Find out what different models of machines can do and
cannot do
▪ The theory of computation

• Computability vs. Complexity

9
 Computation
• Computation is a general term for any type of
information processing that can be
represented as an algorithm precisely
(mathematically).
Examples:
• Adding two numbers in our brains, on a piece of
paper or using a calculator.
• Converting a decimal number to its binary
presentation or vice versa.
• Finding the greatest common divisors of two
numbers.
• …
 Theory of Computation
• The theory of computation studies

• whether (computability theory), and

• how efficiently (complexity theory)

certain problems can be solved on a computer, or rather on a model

of a computer.

• Several equivalent models of computational devices can be used:

• Finite automata.
• Pushdown automata
• Simple while programming language (pseudo-code).
• Turing machines.
• ...
Theory of Computation: A
Historical Perspective
1930s • Alan Turing studies Turing machines
• Decidability
• Halting problem
1940-1950s • “Finite automata” machines studied
• Noam Chomsky proposes the
“Chomsky Hierarchy” for formal
languages
1969 Cook introduces “intractable” problems
or “NP-Hard” problems
1970- Modern computer science: compilers,
computational & complexity theory evolve
Models of Computation

12
Computation

CPU memory

13
temporary memory

input memory
CPU
output memory

Program memory

14
 Example: f (x) = x3

temporary memory

input memory
CPU
output memory
Program memory
compute x x
compute x2  x
15
 f (x) = x3

temporary memory
input memory
x=2
CPU
output memory
Program memory
compute x x
compute x2  x
17
 temporary memory f (x) = x3
z = 2*2 = 4
f (x) = z * 2 = 8
input memory
x=2
CPU
output memory
Program memory
compute x x
compute x2  x
18
 temporary memory f (x) = x3
z = 2*2 = 4
f (x) = z * 2 = 8
input memory
x=2
CPU
f (x) = 8
Program memory
output memory
compute x x
compute x2  x
18
 Automaton
temporary memory

Automaton
input memory
CPU
output memory

Program memory

19
 Different Kinds of Automata
Automata are distinguished by the temporary memory

• Finite Automata: no temporary memory

• Pushdown Automata: stack

• Turing Machines: random access memory

20
 Finite Automaton

temporary memory

Finite input memory

Automaton
output memory

Example: Vending Machines

(small computing power)
21
 Pushdown Automaton
Stack Push, Pop

Pushdown input memory

Automaton
output memory

Example: Compilers for Programming Languages

(medium computing power)
22
 Turing Machine

Random Access Memory

Turing input memory

Machine
output memory

Examples: Any Algorithm

(highest computing power)
24
 Power of Automata

Finite Pushdown Turing

Automata Automata Machine

Less power More power

Solve more
computational problems
24
Languages

25
A language is a set of strings

String: A sequence of letters

Examples: “cat”, “dog”, “house”, …

Defined over an alphabet:

 = a,b,c,…, z

26
 Alphabets and Strings
We will use small alphabets:  = a,b

Strings
a
ab u = ab
abba v = bbbaaa
baba w = abba
aaabbbaabab
27
 String Operations: Concatenation

w = a1a2 …an abba

v = b1b2 … b m bbbaaa

Concatenation

wv = a1a2 …anb1b2 …bm abbabbbaaa

28
 String Operations: Reverse

w = a1a2 …an ababaaabbb

Reverse

w R = an … a 2 a 1 bbbaaababa

29
 String Operations: String Length
w = a1a2 …an
Length: w =n

Examples abba = 4
aa = 2
a =1
30
 String Operations:
Length of Concatenation
uv = u + v

Examples u = aab, u = 3
v = abaab, v = 5

uv = aababaab = 8
uv = u + v = 3 + 5 = 8
31
 String Operations: Empty String
A string with no letters:

Observations:  =0

w = w = w

abba = abba = abba

32
 String Operations: Substring
Substring of string:
a subsequence of consecutive characters

String Substring
abbab ab
abbab abba
abbab b
abbab bbab
33
 String Operations: Prefix and Suffix
Example: abbab
prefixes Suffixes
 abbab w uv
a bbab
prefix
ab bab
suffix
abb ab
abba b
abbab 
35
 String Operations: Power
wn =ww…w
n

Example: (abba) = abbaabba

2

Definition: w0 =

(abba) = 
0

35
 String Operations: The * Operation
* : the set of all possible strings from
alphabet 

 = a,b
* = , a,b, aa, ab,ba,bb, aaa, aab,…

36
 String Operations: The + Operation
+
 : the set of all possible strings from
alphabet  except

 = a,b
* = , a,b, aa, ab,ba,bb, aaa, aab,…

 + = * −
 + = a,b, aa, ab,ba,bb, aaa, aab,…
37
 Languages
A language is any subset of *

Example:  = a,b
* = , a,b, aa, ab,ba,bb, aaa,…

Languages: 
a, aa, aab
{, abba,baba, aa, ab, aaaaaa}
38
 Note that:

Sets  ={}  {}

Set size {} =  = 0
Set size {} = 1
String length
 =0
39
 Another Language Example

An infinite language L = {a b
n n : n  0}


ab
L abb  L
aabb
aaaaabbbbb
40
 Operations on Languages
The usual set operations

a, ab, aaaa∪ bb, ab = {a, ab,bb, aaaa}

a, ab, aaaa∩ bb, ab = {ab}
a, ab, aaaa− bb, ab = a, aaaa
Complement: L = * −L

a,ba= ,b, aa, ab,bb, aaa,…

41
 Operations on Languages: Reverse

Definition: LR ={w R : w L}

Examples: ab, aab,babaR = ba,baa, abab

L = {a b
n n : n  0}

LR = {b a
n n : n  0}
43
Operations on Languages: Concatenation

Definition: L1L2 = xy : x  L1, y  L2

Example: a, ab,bab, aa

= ab, aaa, abb, abaa,bab,baaa

43
 Operations on Languages: Power
Definition: Ln =LL…L
n
Example:

a,b = a,ba,ba,b =
3

aaa, aab, aba, abb,baa,bab,bba,bbb

Special Case: L0 = 

a,bba, aaa0 = 

44
 More Examples

L = {anbn : n  0}

L2 = {anbnambm : n, m  0}

aabbaaabbb  L2

45
 Operations on Languages:
Star-Closure (Kleene *)

Definition: L* = L ∪ L ∪ L
0 1 2…

Example:
, 
a,bb, 
a,bb* =  
 aa, abb,bba,bbbb, 
aaa,aabb, abba, abbbb,…
46
 Operations on Languages:
Positive Closure
Definition: L+ = L ∪ L ∪…
1 2

= L * −

a,bb, 
 
a,bb = aa, abb,bba,bbbb,
+

aaa,aabb, abba, abbbb,…
48
 ToC: Course Introduction

• Recommended Tools:
• UPPAAL

http://www.uppaal.org/

• Tool for the modelling, simulation and verification of

different types of computational algorithms: real-
time, embedded, and concurrent systems e.g.,
embedded processors in mobile phones, microwave
ovens, sensor nodes communicating with the
environment, traffic control systems and so on.
INPUT

UPPAAL