Hierarchy of languages

Non-Recursively Enumerable
Languages

Recursively Enumerable
Languages

Recursive
Languages

Context-Free
Languages
Regular
Languages

1
Language Machine Grammar
Regular Finite Automaton Regular Expression,
Regular Grammar

Context-Free Pushdown Automaton Context-Free

Grammar
Recursively Turing Machine Unrestricted Phrase-
Enumerable Structure Grammar

2
Finite Automata
 Deterministic Finite Automata
∙ Determinism: Always traverses the same
path and yields the same result for the
same input
∙ For every string x, there is a unique path
from initial state and associated with x.
∙ x

∙ x is accepted if and only if this path ends at

an accept state.
 Deterministic Finite Automata
∙ A Finite State Machine consists of:
− A finite set of states
∙ Exactly one “start state”
∙ One or more final (“accepting”) states
− An input alphabet
− A transition function

5
 11 1
0
0,1
1
0111 111 1
0 0

The machine accepts a string if the process

ends in a double circle
 DFA
Mathematical Definition
∙ A Quintuple:

∙ 1) A set of states, Q
∙ 2) An input alphabet, Σ
∙ 3) A transition function, δ: Q x Σ -> Q
∙ 4) An initial state, q0
∙ 5) A set of final states, F ⊆ Q
7
 DFA Example
∙ M = ({q0,q1,q2}, {0,1} , δ, q0, {q1})

∙ δ is defined as:
δ(q0,0) = q0 δ(q0,1) = q1
δ(q1,0) = q0 δ(q1,1) = q2
δ(q2,0) = q2 δ(q2,1) = q1

8
 Transition Table for M

0 1
-q0 q0 q1
+q1 q0 q2
q2 q2 q1

9
Transition Graph for M

• Each state has exactly 2 out-edges (1 for each letter)

What language is this?

10
 Trap States

∙ Sometimes a state can never be exited

− A “black hole” :-)

What language is this?

11
The Complement of a Language
∙ If we have a DFA for a language, L, how
can we form a DFA for its complement?
− Σ* - L
∙ Think of the roles of final states in
recognizing strings…

12
 Complement Example
∙ Find a DFA for the set of all strings except
those that contain “001” as a substring
∙ First build a DFA that accepts strings
containing “001”
∙ Then invert the “acceptability” of each
state
− Now all other strings will be accepted

13
 Solution

Note that the empty string (λ) is accepted

14
 More Practice
∙ Build a DFA that accepts all strings over
{a, b} that start and end in the letter a (but
not just “a”)

∙ Build a DFA for the language over {a, b}

containing an even number of both a’s and
b’s

15
DFA for L

16
DFA for EVEN-EVEN

17
 Even More Practice
∙ Consider binary numbers as input strings:
− Construct a DFA where each state represents the
remainder of the number mod 3
∙ Need 3 states representing 0, 1 and 2, respectively
∙ Making the 0–state final accepts numbers ≡ 0 mod 3
∙ Making the 1–state final accepts numbers ≡ 1 mod 3
∙ Making the 2–state final accepts numbers ≡ 2 mod 3

18
 Strings With Common Prefix
∙ Construct a DFA that accepts a language L
over Σ = {0, 1} such that L is the set of all
strings starting with “101”.
0,1
q 1 q 0 q 1 q
start
0 1 2 3
1
0
absorbing
0
state
q
dead
4
state
0,1
 Strings With Common Suffix
∙ Construct a DFA that accepts a language L
over Σ = {0, 1} such that L is the set of all
strings ending with “101”.

0
q q
0 q 1 q 0
1
1
1 0 1 0
start 0 1
0
1 1
Regular Expressions
 Regular expressions
∙ A regular expression over Σ is an
expression formed using the following
rules:
− The symbol ∅ is a regular expression
− The symbol ε is a regular expression
− For every a ∈ Σ, the symbol a is a regular
expression
− If R and S are regular expressions, so are R+S,
RS and R*.
A language is regular if it is represented
by a regular expression
 Regular Expressions
Regular expressions
describe regular languages

Example:

describes the language

 Recursive Definition
Primitive regular expressions:

Given regular expressions and

Are regular expressions

 Examples

A regular expression:

Not a regular expression:

 Regular Languages
∙ A regular language is one that has a DFA
that accepts it
∙ We proved that the complement of a
regular language is also regular!
∙ To show that a language is regular, we
find a DFA for it
∙ If it isn’t regular, well, that’s another story

26
 Languages of Regular Expressions

: language of regular expression

Example
 Definition

For primitive regular expressions:

 Definition (continued)

For regular expressions and

 Example
Regular expression:
Some Properties of
Regular Languages
 Properties
For regular languages and
we will prove that:

Union:

Are regular
Concatenation:
Languages

Star
:
 We Say:
Regular languages are closed under

Union:

Concatenation:

Star
:
Regular language Regular language

NF NF
A A

Single final state Single final state

Example
 Union
NFA for
 Example
NFA
for
 Concatenation

NFA for
 Example

NFA for
 Star Operation
NFA for
 Example

NFA for
 Example

Regular expression

= { all strings with at least

two consecutive 0 }
 Example

Regular expression

= { all strings without

two consecutive 0 }
 Equivalent Regular Expressions

Definition:

Regular expressions and

are equivalent if
 Theorem

Languages
Regular
Generated by
Languages
Regular Expressions
 Proof - Part 1

1. For any regular expression

the language is regular

Proof by induction on the size of

 Induction Basis
Primitive Regular Expressions:
NFA
s

regular
languages
 Inductive Hypothesis

Assume
for regular expressions and
that
and are regular languages
 Inductive Step
We will prove:

Are regular
Languages
By definition of regular expressions:
 By inductive hypothesis we know:
and are regular languages

We also know:
Regular languages are closed under
union
concatenation

sta
r
Therefore:

Are regular
languages
And trivially:

is a regular language
 Regular Expressions
- Alphabet X = {a, b, c, d}
1) (a + b)*
all strings containing only a and b
1) c(a + b + c)*c2
all strings containing only a, b, and c that begin with c and end with
cc
3) all strings containing only one b
(a+c+d)*b(a+c+d)*
 Regular Expressions
- Alphabet X = {0, 1}
1) (0 + 1)*
the set of all binary strings
1) 031*04
all strings consisting of three 0’s, followed by any number of
1’s, followed by four 0’s
1) 0*1001*
all strings starting with any number of 0’s, followed by 100,
followed by and number of 1’s
 NFA
∙ For any string x, there may exist none or
more than one path from initial state and
associated with x.

∙ x is accepted if there is some path that

ends at a accept state.
 NFA
Mathematical Definition
∙ A Quintuple:
1) A set of states, Q
2) An input alphabet, Σ
3) A transition function, δ: Q x Σ -> 2Q
4) An initial state, q0
5) A set of final states, F ⊆ Q

∙ Note: DFAs are a special case of NFAs

57
Nondeterministic Finite Accepter (NFA)

Alphabet =
Nondeterministic Finite Accepter (NFA)

Alphabet = {a}

Two choices
Nondeterministic Finite Accepter (NFA)

Alphabet =

Two choices
No transition

No transition
First Choice
First Choice
First Choice
First Choice

“accept”
Second Choice
Second Choice
Second Choice

No transition:
the automaton hangs
Second Choice

“reject
”
 NFA for Common Suffix
∙ We can have a simpler representation for
common suffix language using NFA:
1,0 1 0 1
start q q q
q0
1 2 3

∙ Use subset construction to convert it to a

DFA. 0
0 q 1 0
q0 q0 q0q1
start 0 1 q1 0 q2 1 q3
1
 NFA Example
∙ Construct NFAs for the following languages
over the alphabet {a, b, …, z}:
− All strings that contain eat or sea or easy
all all
e a t
start q q q
q0
1 s2 3
y

q4
s
e a
q
q5
6
 Subset Construction Method

Using Subset construction method to convert NFA to

DFA involves the following steps:
∙ For every state in the NFA, determine all reachable states for
every input symbol.
∙ The set of reachable states constitute a single state in the
converted DFA (Each state in the DFA corresponds to a
subset of states in the NFA).
∙ Find reachable states for each new DFA state, until no more
new states can be found.
 Subset Construction Method
Fig1. NFA without λ-transitions
 Subset Construction Method
Fig1. NFA without λ-transitions

3
a b
a
a
a 2 b
a,b
1 5

a,b a
4

b
 Subset Construction Method
Fig1. NFA without λ-transitions

3
a b
a
a
a 2 b Step1
Construct a transition table showing
a,b all reachable states for every state
1 5
for every input signal.
a,b a
4

b
 Subset Construction Method
Fig1. NFA without λ-transitions Fig2. Transition table

3
a b
a
a
a 2 b
a,b
1 5

a,b a
4

b
 Subset Construction Method
Fig1. NFA without λ-transitions Fig2. Transition table

3 q δ(q,a) δ(q,b)
a b {1,2,3,4,5} {4,5}
a 1
a
a 2 b 2 {3} {5}
a,b
1 5 {2}
3 ∅
a,b a 4 {5} {4}
4

b
5 ∅ ∅
 Subset Construction Method
Transition from state q with Transition from state q
Fig1. NFA without λ-transitions input a Fig2. Transitionwith
table
input b

3 q δ(q,a) δ(q,b)
a b Starts here {1,2,3,4,5} {4,5}
a 1
a
a 2 b 2 {3} {5}
a,b
1 5 {2}
3 ∅
a,b a 4 {5} {4}
4

b
5 ∅ ∅
 Subset Construction Method

Fig2. Transition table

q δ(q,a) δ(q,b) Step
1 {1,2,3,4,5} {4,5} 2
The set of states resulting from every
2 {3} {5} transition function constitutes a new
state. Calculate all reachable states
3 ∅ {2} for every such state for every input
signal.
4 {5} {4}

5 ∅ ∅
Fig2. Transition table Fig3. Subset Construction
table
q δ(q,a) δ(q,b) Starts with q δ(q,a) δ(q,b)
Initial state
{1,2,3,4,5} 1 {1,2,3,4,5} {4,5}
1 {4,5}
2 {3} {5}
3 ∅ {2}

4 {5} {4}

5 ∅ ∅
Fig2. Transition table Fig3. Subset Construction
table
q δ(q,a) δ(q,b) Starts with q δ(q,a) δ(q,b)
Initial state
1 {1,2,3,4,5} {4,5} 1 {1,2,3,4,5} {4,5}
{1,2,3,4,5}
2 {3} {5}
3 {2} {4,5}
∅
4 {5} {4}

5 ∅ ∅
Fig2. Transition table Fig3. Subset Construction
table
q δ(q,a) δ(q,b) Starts with q δ(q,a) δ(q,b)
Initial state
1 {1,2,3,4,5} {4,5} 1 {1,2,3,4,5} {4,5}
{1,2,3,4,5}
2 {3} {5}
3 {2} {4,5}
∅
4 {5} {4}

5 ∅ ∅

Step
3
Repeat this process(step2) until no
more new states are reachable.
Fig2. Transition table Fig3. Subset Construction
table
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
{1,2,3,4,5} 1 {1,2,3,4,5} {4,5}
1 {4,5}
{1,2,3,4,5} {1,2,3,4,5} {2,4,5}
2 {3} {5}
{4,5}
3 ∅ {2} {2,4,5}
4 {5} {4}

5 ∅ ∅
Fig2. Transition table Fig3. Subset Construction
table
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
1 {1,2,3,4,5} {4,5} 1 {1,2,3,4,5} {4,5}
{1,2,3,4,5} {1,2,3,4,5} {2,4,5}
2 {3} {5}
{4,5} 5 4
3 ∅ {2}
{2,4,5}
4 {5} {4}
5
5 ∅ ∅ 4
Fig2. Transition table Fig3. Subset Construction
table
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
1 {1,2,3,4,5} {4,5} 1 {1,2,3,4,5} {4,5}
{1,2,3,4,5} {1,2,3,4,5} {2,4,5}
2 {3} {5}
{4,5} 5 4
3 ∅ {2}
{2,4,5} {3,5} 4
4 {5} {4}
5
5 ∅ ∅ 4
{3,5}
Fig2. Transition table Fig3. Subset Construction
table
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
{1,2,3,4,5} 1 {1,2,3,4,5} {4,5}
1 {4,5}
{1,2,3,4,5} {1,2,3,4,5} {2,4,5}
2 {3} {5}
{4,5} 5 4
3 ∅ {2} {3,5} 4
{2,4,5}
4 {5} {4} 5 ∅ ∅
5 ∅ ∅ 4
{3,5}

∅
Fig2. Transition table Fig3. Subset Construction
table
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
1 {1,2,3,4,5} {4,5} 1 {1,2,3,4,5} {4,5}
{1,2,3,4,5} {1,2,3,4,5} {2,4,5}
2 {3} {5}
{4,5} 5 4
3 ∅ {2}
{2,4,5} {3,5} 4
4 {5} {4}
5 ∅ ∅
5 ∅ ∅ 4 5 4
{3,5}
We already got 4 and 5.
So we don’t add them
again.
Fig2. Transition table Fig3. Subset Construction
table
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
1 {1,2,3,4,5} {4,5} 1 {1,2,3,4,5} {4,5}
{1,2,3,4,5} {1,2,3,4,5} {2,4,5}
2 {3} {5}
{4,5} 5 4
3 ∅ {2}
{2,4,5} {3,5} 4
4 {5} {4}
5 ∅ ∅
5 ∅ ∅ 4 5 4
{3,5} ∅ 2

∅
2
Fig2. Transition table Fig3. Subset Construction
table
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
1 {1,2,3,4,5} {4,5} 1 {1,2,3,4,5} {4,5}
{1,2,3,4,5} {1,2,3,4,5} {2,4,5}
2 {3} {5}
{4,5} 5 4
3 ∅ {2}
{2,4,5} {3,5} 4
4 {5} {4}
5 ∅ ∅
5 ∅ ∅ 4 5 4
{3,5} ∅ 2

∅ ∅ ∅
2
Fig2. Transition table Fig3. Subset Construction
table
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
1 {1,2,3,4,5} {4,5} 1 {1,2,3,4,5} {4,5}
{1,2,3,4,5} {1,2,3,4,5} {2,4,5}
2 {3} {5}
{4,5} 5 4
3 ∅ {2}
{2,4,5} {3,5} 4
4 {5} {4}
5 ∅ ∅
5 ∅ ∅ 4 5 4
{3,5} ∅ 2

∅ ∅ ∅
2 3 5
3
Fig2. Transition table Fig3. Subset Construction
table
q δ(q,a) δ(q,b) q δ(q,a) δ(q,b)
1 {1,2,3,4,5} {4,5} 1 {1,2,3,4,5} {4,5}
{1,2,3,4,5} {1,2,3,4,5} {2,4,5}
2 {3} {5}
{4,5} 5 4
3 ∅ {2}
{2,4,5} {3,5} 4
4 {5} {4}
5 ∅ ∅
5 ∅ ∅ 4 5 4
{3,5} ∅ 2

∅ ∅ ∅
Stops here as there are 2 3 5
no more reachable states
3 ∅ 2
 Fig4. Resulting FA after applying
Fig3. Subset Construction Subset Construction to fig1
table
a
q δ(q,a) δ(q,b)
1 {1,2,3,4,5} {4,5} 12345
b 245 a
{1,2,3,4,5} {1,2,3,4,5} {2,4,5} 35

{4,5} 5 4 a
a,b a
{2,4,5} {3,5} 4 b
a b
1 ∅
3
5 ∅ ∅ a,b b
b a
4 5 4
2
{3,5} 2 a
∅ 45 5 b
∅ ∅ ∅ b 4 a

2 3 5
b
3 ∅ 2
 DFA minimization
∙ Steps:
− Remove unreachable states first
− Detect equivalent states
∙ Table-filing algorithm (checklist):
− First, mark X for accept vs. non-accepting
− Pass 1:
∙ Then mark X where you can distinguish by just using one symbol transition
∙ Also mark = whenever states are equivalent.
− Pass 2:
∙ Distinguish using already distinguished states (one symbol)
− Pass 3:
∙ Repeat for 2 symbols (on the state pairs left undistinguished)
∙ …
− Terminate when all entries have been filled
− Finally modify the state diagram by keeping one representative state for every
equivalent class

92
 State Minimization Algorithm
∙ Mark all final states distinguishable from
non-final states (strings of length 0
distinguish these states, obviously)
∙ Repeat until no new unmarked pairs are
marked distinguishable:
◼For all unmarked pairs of states, (p,q):
▪ For each letter, c, of the alphabet Σ:
− If δ(p,c) and δ(q,c) are distinguishable, mark p and q
distinguishable
▪ Combine each group of remaining
mutually indistinguishable states into a
single state 93
Example

94
 Example

∙ Start by grouping final vs. non-final states:

− {q2, q4} vs. {q0, q1, q3}
− Mark all 6 pairings between these groups
distinguishable:
q0 q1 q2 q3 q4

q0 x x

q1 x x

q2 x

q3 x
95
q4
 Example
∙ Check remaining unmarked pairs:
− (q2,q4): δ(q2,0) = q1, δ(q4,0) = q4, => distinguishable
− (q0,q1): δ(q0,0) = q1, δ(q1,0) = q2, => distinguishable
− (q0,q3): δ(q0,0) = q1, δ(q3,0) = q2, => distinguishable
− (q1,q3): δ(q1,0) = δ(q3,0) and δ(q1,1) = δ(q3,1) , =>
indistinguishable

q0 q1 q2 q3 q4

q0 x x x x

q1 x x

q2 x x

q3 x

q4 96
 Result
Combine q1 and q3

97
Thank you!