CS310 : Automata Theory 2020

(1)

CS310 : Automata Theory 2020 Instructor: S. Akshay IIT Bombay, India 1

CS310 : Automata Theory 2020

Lecture 17: Minimization and its applications

Instructor: S. Akshay

IIT Bombay, India

18-02-2020

(2)

Recap

I Automata and algebraic models: DFA, NFA,-NFA, regular expressions.

I Regular languages: All these models accept the same class of languages.

I Conversionsfrom NFA to DFA (Subset construction), -NFA to DFA, Regular expressions to -NFA, DFA to regular expressions

I Applications: text search using automata, regular expressions in GREP, emacs, python etc.

I Properties and limitations of regular languages

I Closure - under union, intersection, complementation, reversal I Pumping lemmaand its application to show non-regularity I Myhill-Nerode theoremand its applications

I Algorithms for Decision problems for automata/regular languages

(3)

Recap

(4)

Recap

(5)

Minimization

Given a DFA, how do we get the one with minimum number of states which accepts the same language?

Algorithm for minimization

I Identify equivalent states using the table-filling algo.

I collapse them and remove redundant states I At end we will obtain a minimal automaton.

(6)

Minimization

I collapse them and remove redundant states

I At end we will obtain a minimal automaton.

(7)

Minimization

I collapse them and remove redundant states I At end we will obtain a minimal automaton.

(8)

Example: A table filling view of the algorithm

q0

start q1 q2 q3

q4 q5 q6 q7

0 1

1 0

0 1

0 1 1

0 0

1

q1

*

q2

* *

q₃

* * *

q4

* * *

q5

* * * *

q₆

* * * * * *

q7

* * * * * *

D q0 q1 q2 q3 q4 q5 q6

Distinguishing words I

I 0 I 1 I 01

(9)

Example: A table filling view of the algorithm

q0

start q1 q2 q3

q4 q5 q6 q7

0 1

1 0

0 1

0 1 1

0 0

1

q1

*

q2 * * q₃

* *

* q4

*

q5

* *

*

q₆

* *

*

* * *

q7

*

* * * *

D q0 q1 q2 q3 q4 q5 q6

I 0 I 1 I 01

(10)

Example: A table filling view of the algorithm

q0

start q1 q2 q3

q4 q5 q6 q7

0 1

1 0

0 1

0 1 1

0 0

1

q1

*

q2 * * q₃ * * * q4

*

* *

q5 * * * *

q₆

* *

*

* q7

*

* *

*

D q0 q1 q2 q3 q4 q5 q6

I 0

I 1 I 01

(11)

Example: A table filling view of the algorithm

q0

start q1 q2 q3

q4 q5 q6 q7

0 1

1 0

0 1

0 1 1

0 0

1

q1 * q2 * * q₃ * * *

q4 * * *

q5 * * * *

q₆

*

* * *

*

q7 * * * * * *

D q0 q1 q2 q3 q4 q5 q6

I 0 I 1

I 01

(12)

Example: A table filling view of the algorithm

q0

start q1 q2 q3

q4 q5 q6 q7

0 1

1 0

0 1

0 1 1

0 0

1

q1 * q2 * * q₃ * * *

q4 * * *

q5 * * * *

q₆ * * * * * *

q7 * * * * * *

D q0 q1 q2 q3 q4 q5 q6

I 0 I 1 I 01

(13)

Example : DFA minimization

After applying the minimization, we obtain.

B0

start B1 B2

B5 B6

0 1

1 0

0 1 1

0

Blocks ={{q₀,q₄}

| {z }

B0

,{q₁,q₇}

| {z }

B1

,{q₂}

| {z }

B2

,{q₃,q₅}

| {z }

B5

,{q₆}

| {z }

B6

}

(14)

Properties of DFA minimization

Theorem

Let Abe a minimized DFA. No DFA smaller than A recognizesL(A).

Proof.

Assume a DFAA⁰ such that A⁰ has fewer states than AandL(A) =L(A⁰).

Therefore, initial statesq₀ andq₀⁰ of Aand A⁰ respectively are equivalent. claim: All states of Aare equivalent to some state ofA⁰.

We know all states ofA are reachable from its initial state(why?). Letq be a state inA.

Let wordw takeAto q.

Let wordw takeA⁰ to some state q⁰.

q andq⁰ must be equivalent. Otherwise,q0 andq⁰₀ are not equivalent.^(why?)

q₀

start start q₀⁰

A A⁰

q w

q⁰ w

...

(15)

Properties of DFA minimization

Theorem

Proof.

Assume a DFA A⁰ such that A⁰ has fewer states than AandL(A) =L(A⁰).

Therefore, initial statesq₀ andq⁰₀ of Aand A⁰ respectively are equivalent. claim: All states of Aare equivalent to some state ofA⁰.

q andq⁰ must be equivalent. Otherwise,q0 andq⁰₀ are not equivalent.^(why?)

q₀

start start q₀⁰

A A⁰

q w

q⁰ w

...

(16)

Properties of DFA minimization

Theorem

Proof.

Therefore, initial states q₀ andq⁰₀ of Aand A⁰ respectively are equivalent.

claim: All states of Aare equivalent to some state ofA⁰.

q and q⁰ must be equivalent. Otherwise, q0 andq⁰₀ are not equivalent.^(why?)

q₀

start start q₀⁰

A A⁰

q w

q⁰ w

...

(17)

Properties of DFA minimization

Theorem

Proof.

q₀

start start q₀⁰

A A⁰

q w

q⁰ w

...

(18)

Properties of DFA minimization

Theorem

Proof.

We know all states ofAare reachable from its initial state^(why?).

Letq be a state inA. Let wordw takeAto q.

q₀

start start q₀⁰

A A⁰

q w

q⁰ w

...

(19)

Properties of DFA minimization

Theorem

Proof.

We know all states ofAare reachable from its initial state^(why?). Letq be a state inA.

q₀

start start q₀⁰

A A⁰

q

w

q⁰ w

...

(20)

Properties of DFA minimization

Theorem

Proof.

q₀

start start q₀⁰

A A⁰

q w

q⁰ w

...

(21)

Properties of DFA minimization

Theorem

Proof.

q₀

start start q₀⁰

A A⁰

q w

q⁰ w

...

(22)

Properties of DFA minimization

Theorem

Proof.

q and q⁰ must be equivalent. Otherwise, q0 andq⁰₀ are not equivalent.^(why?) q₀

start start q₀⁰

A A⁰

q w

q⁰ w

...

(23)

Properties of DFA minimization

Proof(Contd.)

Due to the pigeonhole principle, there are statesq₁ andq₂ of Asuch that they are equivalent to the same state of A⁰.

Therefore,q1 andq2 are equivalent.

SinceAis minimized, no two states ofA are equivalent. Contradiction. In fact, the minimized DFA is unique up to renaming of states. What is its link to the Myhill-Nerode theorem?

(24)

Properties of DFA minimization

Proof(Contd.)

Therefore, q1 andq2 are equivalent.

SinceAis minimized, no two states ofA are equivalent. Contradiction. In fact, the minimized DFA is unique up to renaming of states. What is its link to the Myhill-Nerode theorem?

(25)

Properties of DFA minimization

Proof(Contd.)

Since Ais minimized, no two states ofA are equivalent. Contradiction.

In fact, the minimized DFA is unique up to renaming of states. What is its link to the Myhill-Nerode theorem?

(26)

Properties of DFA minimization

Proof(Contd.)

Since Ais minimized, no two states ofA are equivalent. Contradiction.

In fact, the minimized DFA is unique up to renaming of states. What is its link to the Myhill-Nerode theorem?

(27)

Recall: Myhill-Nerode relation

Right congruence

An equivalence relation ≡on Σ^∗ is called aright congruenceif∀x,y ∈Σ^∗ and w ∈Σ^∗ x ≡y =⇒ x·w ≡y·w.

Refinement

An equivalence relation≡on Σ^∗ is said torefine a language Lifx ≡y then x∈Liff y ∈L.

Finite index

An equivalence relation≡on Σ^∗ is said to havefinite index if the number of equivalence classes of≡is finite.

Myhill-Nerode relation

An equivalence relation≡is called aMyhill-Nerode relation for languageLif it is a right congruence, it refinesLand it is of finite index.

(28)

Recall: Myhill-Nerode relation

Right congruence

Refinement

An equivalence relation ≡on Σ^∗ is said torefine a language Lifx ≡y then x ∈Liff y ∈L.

Finite index

An equivalence relation≡on Σ^∗ is said to havefinite index if the number of equivalence classes of≡is finite.

(29)

Recall: Myhill-Nerode relation

Right congruence

Refinement

Finite index

An equivalence relation ≡on Σ^∗ is said to havefinite index if the number of equivalence classes of ≡is finite.

(30)

Recall: Myhill-Nerode relation

Right congruence

Refinement

Finite index

An equivalence relation ≡on Σ^∗ is said to havefinite index if the number of equivalence classes of ≡is finite.

An equivalence relation ≡is called aMyhill-Nerode relation for languageLif it is a right congruence, it refines Land it is of finite index.

(31)

Link between Myhill-Nerode and minimization

Given an arbitrary language L over Σ. Consider the relation≡_L defined by x ≡_Ly iff for all z ∈Σ^∗, either both xz,yz ∈L or bothxz,yz6∈L.

I It is an equivalence relation. I It is right congruent, refines L. Theorem

IfLis regular then≡_L is of finite-index.

Exercise 1: prove this! Hint: show that any Myhill-Nerode relation≡for L must refine≡_L, i.e., any equiv class of≡_L is a union of equiv classes of ≡.

I Thus, the DFA constructed from ≡_L is “the” canonical DFA! I Exercise 2 (easy): Show that this DFA has minimum no. of states I Exercise 3 (star!): Show that there is a 1-1 correspondance between this

DFA and the minimized DFA.

(32)

Link between Myhill-Nerode and minimization

I It is an equivalence relation.

I It is right congruent, refines L. Theorem

(33)

Link between Myhill-Nerode and minimization

I It is right congruent, refines L.

Theorem

(34)

Link between Myhill-Nerode and minimization

Theorem

IfL is regular then≡_L is of finite-index.

Exercise 1: prove this!

Hint: show that any Myhill-Nerode relation≡for L must refine≡_L, i.e., any equiv class of≡_L is a union of equiv classes of ≡.

(35)

Link between Myhill-Nerode and minimization

Theorem

Exercise 1: prove this! Hint: show that any Myhill-Nerode relation≡for L must refine ≡_L, i.e., any equiv class of≡_L is a union of equiv classes of ≡.

(36)

Link between Myhill-Nerode and minimization

Theorem

I Thus, the DFA constructed from≡_L is “the” canonical DFA!

I Exercise 2 (easy): Show that this DFA has minimum no. of states I Exercise 3 (star!): Show that there is a 1-1 correspondance between this

(37)

Link between Myhill-Nerode and minimization

Theorem

I Exercise 2 (easy): Show that this DFA has minimum no. of states

I Exercise 3 (star!): Show that there is a 1-1 correspondance between this DFA and the minimized DFA.

(38)

Link between Myhill-Nerode and minimization

Theorem

I Exercise 2 (easy): Show that this DFA has minimum no. of states I Exercise 3 (star!): Show that there is a 1-1 correspondance between this

(39)

Applications: Minimization in Natural Language Processing!

Finite state transducers

I A DFA in which you read an input and produce an output!

I Input from Σ, output from Γ.

I In fact after each input letter, output may be string from Γ^∗. I As usual, output depends on state of machine and letter being read.

(40)

Applications: Minimization in Natural Language Processing!

Exercise 1: Define this formally.

(41)

Applications: Minimization in Natural Language Processing!

I T = (Q,Σ,Γ, δ,q₀) where I Q is finite set of states

I Σ,Γ are input and output alphabets I δ :Q×Σ→Q×Γ^∗

(42)

Applications: Minimization in Natural Language Processing!

I T = (Q,Σ,Γ, δ,q₀) where I Q is finite set of states

I Σ,Γ are input and output alphabets I δ :Q×Σ→Q×Γ^∗

Example: Input w ∈ {a,b}^∗, Output: string w⁰ ∈ {0,1}such that

#0(w⁰) = 2.#a(w) and #1(w⁰) = #_b(w)

(43)

Applications: Minimization in NLP

I Text processing: Given input as English alphabet, output can be capitalized words.

I Translation: Given input in English, output can be in Gujarati.

I Speech processing: Given input in speech patterns/sounds, output can be English phrases

Applications use FST models and ideally one wants to construct the smallest model. So build a large one and minimize it!

References in piazza.

(44)

Applications: Minimization in NLP

(45)

Applications: Minimization in NLP

(46)

Applications: Minimization in NLP

(47)