Finite State Automata

(1)

CS 208: Automata Theory and Logic

Lecture 2: Finite State Automata Ashutosh Trivedi

A

start B

b

∀x(La(x)→ ∃y.(x<y)∧Lb(y))

a

b

a

Department of Computer Science and Engineering, Indian Institute of Technology Bombay.

(2)

Ashutosh Trivedi – 2 of 20

Computation With Finitely Many States

Non-determinism

(3)

Machines and their Mathematical Abstractions

Finite instruction machine with finite memory(Finite State Automata)

S

start C

no coin coin

ready dispense not ready

Finite instruction machine with unbounded memory(Turing machine)

. . . b

⊥ . . . $

P Q

b/a,R

a/⊥,L

(4)

Finite State Automata

start S C

no coin coin

ready dispense not ready

– Introduced first by two neuro-psychologistsWarren S. McCulloughandWalter Pittsin 1943 as a model for human brain!

– Finite automata can naturally model

microprocessorsand evensoftware programs working on variables with bounded domain – Capture so-calledregularsets of sequences that

occur in many different fields (logic, algebra, regEx) – Nice theoretical properties

– Applications in digital circuit/protocol verification, compilers, pattern recognition, etc.

(5)

Calculemus! — Gottfried Wilhelm von Leibniz

Let us observe our mental process while we compute the following: – Recognize a string of aneven length.

– Recognize a binary string of aneven number of 0’s. – Recognize a binary string of anodd number of 0’s. – Recognize a string thatcontains your roll number. – Recognize a binary (decimal) string that is amultiple of 2. – Recognize a binary (decimal) string that is amultiple of 3. – Recognize a string withwell-matched parenthesis. – Recognize a#separated string of the formw#w. – Recognize a string witha prime numberof 1’s

(6)

Calculemus! — Gottfried Wilhelm von Leibniz

Let us observe our mental process while we compute the following:

– Recognize a string of aneven length.

– Recognize a binary string of aneven number of 0’s. – Recognize a binary string of anodd number of 0’s. – Recognize a string thatcontains your roll number. – Recognize a binary (decimal) string that is amultiple of 2. – Recognize a binary (decimal) string that is amultiple of 3. – Recognize a string withwell-matched parenthesis. – Recognize a#separated string of the formw#w. – Recognize a string witha prime numberof 1’s

(7)

Calculemus! — Gottfried Wilhelm von Leibniz

– Recognize a binary string of aneven number of 0’s.

– Recognize a binary string of anodd number of 0’s. – Recognize a string thatcontains your roll number. – Recognize a binary (decimal) string that is amultiple of 2. – Recognize a binary (decimal) string that is amultiple of 3. – Recognize a string withwell-matched parenthesis. – Recognize a#separated string of the formw#w. – Recognize a string witha prime numberof 1’s

(8)

Calculemus! — Gottfried Wilhelm von Leibniz

– Recognize a binary string of anodd number of 0’s.

– Recognize a string thatcontains your roll number. – Recognize a binary (decimal) string that is amultiple of 2. – Recognize a binary (decimal) string that is amultiple of 3. – Recognize a string withwell-matched parenthesis. – Recognize a#separated string of the formw#w. – Recognize a string witha prime numberof 1’s

(9)

Calculemus! — Gottfried Wilhelm von Leibniz

– Recognize a string thatcontains your roll number.

– Recognize a binary (decimal) string that is amultiple of 2. – Recognize a binary (decimal) string that is amultiple of 3. – Recognize a string withwell-matched parenthesis. – Recognize a#separated string of the formw#w. – Recognize a string witha prime numberof 1’s

(10)

Calculemus! — Gottfried Wilhelm von Leibniz

– Recognize a binary (decimal) string that is amultiple of 2.

– Recognize a binary (decimal) string that is amultiple of 3. – Recognize a string withwell-matched parenthesis. – Recognize a#separated string of the formw#w. – Recognize a string witha prime numberof 1’s

(11)

Calculemus! — Gottfried Wilhelm von Leibniz

– Recognize a string withwell-matched parenthesis. – Recognize a#separated string of the formw#w. – Recognize a string witha prime numberof 1’s

(12)

Calculemus! — Gottfried Wilhelm von Leibniz

– Recognize a string withwell-matched parenthesis.

– Recognize a#separated string of the formw#w. – Recognize a string witha prime numberof 1’s

(13)

Calculemus! — Gottfried Wilhelm von Leibniz

– Recognize a#separated string of the formw#w.

– Recognize a string witha prime numberof 1’s

(14)

Calculemus! — Gottfried Wilhelm von Leibniz

– Recognize a#separated string of the formw#w.

– Recognize a string witha prime numberof 1’s

(15)

Finite State Automata

Automaton acceptingstrings of even length:

start E O

0,1

Automaton acceptingstrings with an even number of 1’s:

E

start O

0 1

1 0

Automaton acceptingeven strings (multiple of 2):

E

start O

0 1

(16)

Finite State Automata

E

start O

0,1

Afinite state automatonis atuple(S,Σ, δ,s0,F), where:

– Sis afinite setcalled thestates;

– Σis afinite setcalled thealphabet;

– δ:S×Σ→Sis thetransition function;

– s0∈Sis thestart state; and – F⊆Sis the set ofaccept states.

Example: The automaton in the figure above can be represented as (S,Σ, δ,s0,F)whereS={E,O},Σ ={0,1},s0=E,F={E}, and transition functionδis such that

– δ(E,0) =O,δ(E,1) =0, andδ(O,0) =E,δ(O,1) =E.

(17)

Finite State Automata

E

start O

0,1

Afinite state automatonis atuple(S,Σ, δ,s0,F), where:

Example: The automaton in the figure above can be represented as (S,Σ, δ,s0,F)whereS={E,O},Σ ={0,1},s0=E,F={E}, and transition functionδis such that

– δ(E,0) =O,δ(E,1) =0, andδ(O,0) =E,δ(O,1) =E.

(18)

State Diagram

Let’s draw the state diagram of the following automaton(S,Σ, δ,s1,F): – S={s1,s2,s3}

– Σ ={0,1},

– δis given in a tabular form below:

S 0 1

s1 s1 s2

s2 s3 s2

s3 s2 s2

– s1is the initial state, and – F={s2}.

What does it accept?

(19)

State Diagram

Let’s draw the state diagram of the following automaton(S,Σ, δ,s1,F): – S={s1,s2,s3}

– Σ ={0,1},

– δis given in a tabular form below:

S 0 1

s1 s1 s2

s2 s3 s2

s3 s2 s2

– s1is the initial state, and – F={s2}.

What does it accept?

(20)

Semantics of the finite state automata

Afinite state automaton(DFA) is atuple(S,Σ, δ,s0,F), where:

– Acomputationor arunof a DFA on a stringw=a0a1. . .an−1is the finite sequence

s0,a1s1,a2, . . . ,an−1,sn

wheres0is the starting state, andδ(si−1,ai) =si+1.

– A run isacceptingif the last state of the unique computation is an accept state, i.e.sn∈F.

– Languageof a DFAA

L(A) ={w : the unique run ofAonwis accepting}.

Definition (Regular Languages)

Alanguageis calledregularif it is accepted by a finite state automaton.

(21)

Semantics of the finite state automata

Afinite state automaton(DFA) is atuple(S,Σ, δ,s0,F), where:

– Acomputationor arunof a DFA on a stringw=a0a1. . .an−1is the finite sequence

s0,a1s1,a2, . . . ,an−1,sn

wheres0is the starting state, andδ(si−1,ai) =si+1.

– A run isacceptingif the last state of the unique computation is an accept state, i.e.sn∈F.

– Languageof a DFAA

L(A) ={w : the unique run ofAonwis accepting}.

Definition (Regular Languages)

Alanguageis calledregularif it is accepted by a finite state automaton.

(22)

Properties of Regular Languages

LetAandBbe languages (remember they are sets). We define the following operations on them:

– Union:A∪B={w : w∈Aorw∈B}

– Concatenation:AB={wv : w∈Aandv∈B}

– Closure(Kleene Closure, or Star):

A^∗={w1w2. . .wk : k≥0 andwi∈A}. In other words:

A^∗=∪_i≥0Aⁱ

whereA⁰ =∅,A¹=A,A²=AA, and so on.

Define the notion of a set being closed under an operation (say,Nand×).

Theorem

The class of regular languages is closed under union, concatenation, and Kleene closure.

(23)

Properties of Regular Languages

LetAandBbe languages (remember they are sets). We define the following operations on them:

– Union:A∪B={w : w∈Aorw∈B}

– Concatenation:AB={wv : w∈Aandv∈B}

– Closure(Kleene Closure, or Star):

A^∗={w1w2. . .wk : k≥0 andwi∈A}. In other words:

A^∗=∪_i≥0Aⁱ

whereA⁰ =∅,A¹=A,A²=AA, and so on.

Define the notion of a set being closed under an operation (say,Nand×).

Theorem

(24)

Closure under Union

Lemma

The class of regular languages is closed under union.

Proof.

– LetA1andA1be regular languages.

– LetM1= (S1,Σ, δ₁,s1,F1)andM2= (S2,Σ, δ₂,s2,F2)be finite automata accepting these languages.

– Simulate both automata together!

– The languageA∪Bis accept by the resulting finite state automaton, and hence isregular.

Class Exercise: Extend this construction for intersection.

(25)

Closure under Union

Lemma

Proof.

(26)

Closure under Union

Lemma

Proof.

(27)

Closure under Union

Lemma

Proof.

(28)

Closure under Concatenation

Lemma

The class of regular languages is closed under concatenation.

Proof.

(Attempt).

– How can we find an automaton that accepts the concatenation?

– Does this automaton fit our definition of a finite state automaton?

– Determinism vs Non-determinism

(29)

Computation With Finitely Many States

Non-determinism

(30)

Nondeterministic Finite State Automata

Michael O. Rabin Dana Scott

(31)

Non-deterministic Finite State Automata

s1

start s2 s3 s4

0,1

1 0, ε 1

0,1

Anon-deterministic finite state automaton(NFA) is atuple(S,Σ, δ,s0,F), where:

– Sis afinite setcalled thestates; – Σis afinite setcalled thealphabet;

– δ:S×(Σ∪ {ε})→2^Sis thetransition function; – s0∈Sis thestart state; and

– F⊆Sis the set ofaccept states.

Example: Difference between a deterministic vs a non-deterministic computation (above NFA on a string 010110).

(32)

Non-deterministic Finite State Automata

s1

start s2 s3 s4

0,1

1 0, ε 1

0,1

– δ:S×(Σ∪ {ε})→2^Sis thetransition function;

(33)

Non-deterministic Finite State Automata

s1

start s2 s3 s4

0,1

1 0, ε 1

0,1

(34)

Non-deterministic Finite Automata: Semantics

– Acomputationor arunof a NFA on a stringw=a0a1. . .an−1is a finite sequence

s0,r1s1,r2, . . . ,rk−1,sn

wheres0is the starting state, andsi+1∈δ(si−1,ri)and r0r1. . .rk−1=a0a1. . .an−1.

– Unlike DFA, there can be multiple runs of an NFA on a string.

– A run isacceptingif the last state of some computation is an accepting statesn∈F.

– Languageof a NFAA L(A) ={w : some run ofAonwis accepting}.

(35)

NFA vs DFA

NFA are often more convenient to design than DFA, e.g.:

– {w : wcontains 1 in the third last position}. – {w: : wis a multiple of 2 or a multiple of 3}. – Union and intersection of two DFAs as an NFA – Some other examples

(36)

Equivalence of NFA and DFA

Theorem

Every non-deterministic finite automaton has an equivalent (accepting the same language) deterministic finite automaton.

Proof.

– For the sake of simplicity assume NFA isε-free.

– Design a DFA that simulates a given NFA.

– Note that NFA can be in a number of states at any given time – How are the states of the corresponding DFA?

– Define initial state and accepting states – Define the transition function

Determinize the following automaton:

s1

start s2 s3 s4

0,1

1 0,1 0,1

(37)

Equivalence of NFA and DFA

Theorem

Every non-deterministic finite automaton has an equivalent (accepting the same language) deterministic finite automaton.

Proof.

– For the sake of simplicity assume NFA isε-free.

– Design a DFA that simulates a given NFA.

– Note that NFA can be in a number of states at any given time – How are the states of the corresponding DFA?

– Define initial state and accepting states – Define the transition function

Determinize the following automaton:

s1

start s2 s3 s4

0,1

1 0,1 0,1

(38)

Extension

Exercise: Extend the previous construction in the presence ofε-transitions.

Hint:ε-closure of a set of states.

(39)

Closure under Regular Operations

Theorem

Proof.

– We have already seen the closure under union as a DFA and as an NFA.

– Concatenation and Kleene closure can easily be defined as an NFA usingε-transitions.

– The theorem follows from the equivalence of NFA and DFA.