Automata and Complexity Theory
(CoSc3102
CoSc3102)
Chapter 2
Introduction
Definitions
• Symbol – An atomic unit, such as a digit, character, lower-
lower
case letter, etc. Sometimes a word. [Formal language does
not deal with the “meaning” of the symbols.]
• Alphabet – A finite set of symbols, usually denoted by Σ.
Σ = {0, 1} Σ = {0, a, 4} Σ = {a, b, c, d}
• String – A finite length sequence of symbols, presumably
from some alphabet.
Alphabets and strings
• A common way to talk about words, number, pairs of words, etc.
is by representing them as strings
• To define strings, we start with an alphabet
An alphabet is a finite set of symbols.
• Examples
S1 = {a, b, c, d, …, z}:: the set of letters in English
S2 = {0, 1, …, 9}:: the set of (base 10) digits
S3 = {a, b, …, z, #}:: the set of letters plus the
special symbol #
S4 = {(, )}:: the set of open and closed brackets
Strings
A string over alphabet S is a finite sequence
of symbols in S.
• The empty string will be denoted by e (epsilon)
• Examples
abfbz is a string over S1 = {a, b, c, d, …, z}
9021 is a string over S2 = {0, 1, …, 9}
ab#bc is a string over S3 = {a, b, …, z, #}
))()(() is a string over S4 = {(,
{ )}
Strings
Let: u=ε w = 0110 y = 0aa x = aabcaa z = 111
concatenation: wz = 0110111
length: |w| = 4 |x| = 6 but |u| = 0
reversal: yR = aa0
Substring:: Sequence of symbols form any part of the given
string. Ex: 11 is substring of w
Prefix:: A substring with the sequence of beginning symbols of
a given string. Ex: 0 in w
Suffix: A substring with the sequence of ending symbols of a
given string Ex: 10 in w
Strings
Some special sets of strings
• Σ* All strings of symbols from Σ
• Σ+ Σ* - {ε}
Example: Σ = {0, 1}
• Σ** = {ε,
{ , 0, 1, 00, 01, 10, 11, 000, 001,…}
• + = {0, 1, 00, 01, 10, 11, 000, 001,…}
Σ+
What is Formal Language ?
A (formal) language is a set of strings over an alphabet.
alphabet
i.e. any subset L of Σ*
• Classes of formal languages (e.g., regular, context-free,
context
context-sensitive,
sensitive, recursive, recursively enumerable).
• Formal languages are related to programming languages and
natural languages
Formal Language Examples:
Σ = {0, 1}
L = {x | x is in Σ** and x contains an even number of 0’s}
Σ = {0, 1, 2,…, 9, .}
L = {x | x is in Σ** and x forms a finite length real number}
= {0, 1.5, 9.326,…}
Σ = {a, b, c,…, z, A, B,…, Z}
L = {x | x is in Σ** and x is a CPP reserved word}
= {while, for, if, int, …}
Formal Language Examples:
Σ = {CPP reserved words} U { (, ), ., :, ;,…} U {Legal CPP
identifiers}
L = {x | x is in Σ** and x is a syntactically correct CPP
program}
Σ = {English words}
L = {x | x Σ** and x is a syntactically correct English
sentence}
What is automata theory ?
• Automata theory is the study of abstract computational devices
• Abstract devices are (simplified) models of real computations
• Computations happen everywhere: On your laptop, on your cell
phone, in nature, …
• Why do we need abstract models?
A simple “computer”
BATTERY
input: switch
output: light bulb
actions: flip switch
states: on, off
A simple “computer”
BATTERY start off on
input: switch
output: light bulb bulb is on if and only if there was
an odd number of flips
actions: f for “flip switch”
states: on, off
Another “computer”
1
1 start off off
1
2 2 2 2
BATTERY
1
2
off on
1
inputs: switches 1 and 2
actions: 1 for “flip switch 1” bulb is on if and only if both
actions: 2 for “flip switch 2” switches were flipped an odd
number of times
states: on, off
Another Example
• A state diagram for a simple Game Enemy model
Wander - player is with in sight - Attack
Attack - player is out of sight - Wander
Attack - player is attacking - Evade
Evade - player is idle - Attack
Different kinds of automata
• This was only some examples of a computational device, and
there are others
• We will look at different devices, and look at the following
questions:
– What can a given type of device compute, and what are its limitations?
– Is one type of device more powerful than another?
Some devices we will see
finite automata Devices with a finite amount of memory.
Used to model “small” computers.
push-down automata Devices with infinite memory that can be accessed in
a restricted way.
Used to model parsers, etc.
Turing Machines Devices with infinite memory.
Used to model any computer.
Preliminaries of automata theory
• How do we formalize the question
Can device A solve problem B?
• First, we need a formal way of describing the problems that we
are interested in solving
