The document describes deterministic finite automata and regular languages. It defines the components of a DFA including states, input alphabet, transition function, initial state, and accepting states. It also explains how a DFA accepts or rejects strings based on its transition graph and definitions.
The document describes deterministic finite automata and regular languages. It defines the components of a DFA including states, input alphabet, transition function, initial state, and accepting states. It also explains how a DFA accepts or rejects strings based on its transition graph and definitions.
The document describes deterministic finite automata and regular languages. It defines the components of a DFA including states, input alphabet, transition function, initial state, and accepting states. It also explains how a DFA accepts or rejects strings based on its transition graph and definitions.
The document describes deterministic finite automata and regular languages. It defines the components of a DFA including states, input alphabet, transition function, initial state, and accepting states. It also explains how a DFA accepts or rejects strings based on its transition graph and definitions.
M = ( Q, Σ, δ , q0 , F ) Q : set of states Σ : input alphabet λ ∉Σ δ : transition function q0 : initial state F : set of accepting states Set of States Q Example
Q = { q0 , q1, q2 , q3 , q4 , q5 } a, b
q5 a a, b b a b q0 a q1 b q2 b q3 a q4 Input Alphabet Σ
λ ∉Σ :the input alphabet never contains λ
Example Σ = { a, b} a, b
q5 b a a, b a b q0 a q1 b q2 b q3 a q4 Initial State q0
Example a, b
q5 a a, b b a b q0 a q1 b q2 b q3 a q4 Set of Accepting States F ⊆ Q
Example F = { q4 } a, b
q5 a a, b b a b q0 a q1 b q2 b q3 a q4 Transition Function δ :Q×Σ → Q
δ (q , x ) = q ′ x q q′
Describes the result of a transition
from state q with symbol x Example: δ ( q0 , a ) = q1
a, b
q5 b a a, b a b q0 a q1 b q2 b q3 a q4 δ ( q0 , b ) = q5
a, b
q5 b a a, b a b q0 a q1 b q2 b q3 a q4 δ ( q2 , b ) = q3
a, b
q5 b a a, b a b q0 a q1 b q2 b q3 a q4 Transition Table for δ symbols δ a b q0 q1 q5 q1 q5 q2 states
q2 q5 q3 a, b q3 q4 q5 q4 q5 q5 q5 q5 q5 q5 a, b b a a b q0 a q1 b q2 b q3 a q4 Extended Transition Function δ :Q × Σ → Q * *
δ (q ,w ) = q ′ *
Describes the resulting state
after scanning string w from state q Example: δ ( q0 , ab ) = q2 *
a, b
q5 b a a, b a b q0 a q1 b q2 b q3 a q4 δ ( q0 , abbbaa ) = q5 *
a, b
q5 b a a, b a b q0 a q1 b q2 b q3 a q4 δ ( q1 , bba ) = q4 *
a, b
q5 b a a, b a b q0 a q1 b q2 b q3 a q4 Special case:
for any state q
δ (q , λ ) = q * In general: δ ( q ,w ) = q ′ *
implies that there is a walk of transitions
w = σ 1σ 2 σ k σ1 σ2 σk q q′ states may be repeated
q w q′ Language Accepted by DFA
Language of DFA M: it is denoted as L ( M ) and contains all the strings accepted by M
We say that a language L ′
is accepted (or recognized) ( ) by DFA M if L M = L ′ For a DFA M = ( Q, Σ, δ , q0 , F ) Language accepted by M: L ( M ) = {w ∈ Σ : δ ( q0 ,w ) ∈ F } * *
q0 w q′ q′ ∈ F Language rejected by M:
L ( M ) = {w ∈ Σ : δ ( q0 ,w ) ∉ F } * *
q0 w q′ q′ ∉ F More DFA Examples Σ = {a , b } a, b a, b
q0 q0
L (M ) = { } L (M ) = Σ *
Empty language All strings
Σ = {a , b }
a, b
q0 a, b q0
L (M ) = { λ } Language of the empty string Σ = {a , b } L( M ) = { all strings with prefix ab } a, b
q0 a q1 b q2
b a accept
q3 a, b L ( M ) = { all binary strings containing substring 001 }
0,1 1 0 1
λ 0 0 00 1 001 0 L ( M ) = { all binary strings without substring 001 }
1 0 0,1 1
λ 0 1 0 00 001
0 { L(M ) = awa : w ∈ {a , b } * } a b b q0 a q2 q3
b a q4
a, b Regular Languages Definition: A language L is regular if there is a DFA M that accepts it ( L(M ) = L )
The languages accepted by all DFAs
form the family of regular languages Example regular languages:
{ abba} { λ , ab, abba}
{a b : n ≥ 0} {awa : w ∈ {a , b } } n *
{ all strings in {a,b}* with prefix ab }
{ all binary strings without substring 001} {x : x ∈ {1} and x is even} *
{ } { λ } {a , b } *
There exist automata that accept these
languages (see previous slides). There exist languages which are not Regular:
n n L= {a b : n ≥ 0}
ADDITION = {x + y = z : x = 1 , y = 1 , z = 1 , n m k
