# Languages and Finite Automata - LSU Deterministic Finite Automata And Regular Languages Costas Busch - LSU 1 Deterministic Finite Automaton (DFA) Input Tape String Finite Automaton Costas Busch - LSU Output Accept or

Reject 2 Transition Graph a, b q5 a b a b q0 a q1 b q2 b q3 a initial state state transition Costas Busch - LSU a, b

q4 accepting state 3 Alphabet {a,b } a, b q5 a b a b q0 a q1 b q2 b q3 a a, b

q4 For every state, there is a transition for every symbol in the alphabet Costas Busch - LSU 4 Initial Configuration Input Tape a b b a Input String a, b q5 a b a b

q0 a q1 b q2 b q3 a a, b q4 Initial state Costas Busch - LSU 5 Scanning the Input a b b a head a, b q5 a b a

b q0 a q1 b q2 b q3 a Costas Busch - LSU a, b q4 6 a b b a a, b q5 a b a b q0 a q1 b q2 b q3 a

Costas Busch - LSU a, b q4 7 a b b a a, b q5 a b a b q0 a q1 b q2 b q3 a Costas Busch - LSU a, b

q4 8 Input finished a b b a a, b q5 a b a b q0 a q1 b q2 b q3 a a, b q4 accept Last state determines the outcome

Costas Busch - LSU 9 A Rejection Case a b a Input String a, b q5 a b a b q0 a q1 b q2 b q3 a Costas Busch - LSU a, b

q4 10 a b a a, b q5 a b a b q0 a q1 b q2 b q3 a Costas Busch - LSU a, b q4 11

a b a a, b q5 a b a b q0 a q1 b q2 b q3 a Costas Busch - LSU a, b q4 12 Input finished a b a

a, b q5 a b a b q0 a q1 b q2 b q3 a reject a, b q4 Last state determines the outcome Costas Busch - LSU 13 Another Rejection Case Tape is empty

Input Finished (no symbol read) a, b q5 a b a b q0 a q1 b q2 b q3 a a, b q4 reject

Costas Busch - LSU 14 This automaton accepts only one string Language Accepted: L abba a, b q5 a b a b q0 a q1 b q2 b q3 a Costas Busch - LSU a, b q4

15 To accept a string: all the input string is scanned and the last state is accepting To reject a string: all the input string is scanned and the last state is non-accepting Costas Busch - LSU 16 Another Example L , ab, abba a, b q5 a b

a b q0 a q1 b q2 b q3 a Accept state Accept state Costas Busch - LSU a, b q4 Accept state 17 Empty Tape

Input Finished a, b q5 a b a b q0 a q1 b q2 b q3 a a, b q4 accept Costas Busch - LSU 18

Another Example a, b a q0 b q1 Accept state Costas Busch - LSU a, b q2 trap state 19

a a b Input String a, b a q0 b q1 Costas Busch - LSU a, b q2 20 a a b

a, b a q0 b q1 Costas Busch - LSU a, b q2 21 a a b a, b

a q0 b q1 Costas Busch - LSU a, b q2 22 Input finished a a b a, b a

q0 accept b q1 Costas Busch - LSU a, b q2 23 A rejection case b a b Input String a, b

a q0 b q1 Costas Busch - LSU a, b q2 24 b a b a, b a

q0 b q1 Costas Busch - LSU a, b q2 25 b a b a, b a q0

b q1 Costas Busch - LSU a, b q2 26 Input finished b a b a, b a q0 b

q1 a, b q2 reject Costas Busch - LSU 27 Language Accepted: n L {a b : n 0} a, b a

q0 b q1 Costas Busch - LSU a, b q2 28 Another Example Alphabet: {1} 1 q0

q1 1 Language Accepted: * EVEN {x : x and x is even} { , 11, 1111 , 111111 , } Costas Busch - LSU 29 Formal Definition Deterministic Finite Automaton (DFA) M Q, , , q0 , F Q : set of states : input alphabet

: transition function q0 : initial state F : set of accepting states Costas Busch - LSU 30 Set of States Q Example Q q0 , q1, q2 , q3 , q4 , q5 a, b q5 a b

a b q0 a q1 b q2 b q3 a Costas Busch - LSU a, b q4 31 Input Alphabet :the input alphabet never contains empty string Example a, b a, b

q5 a b a b q0 a q1 b q2 b q3 a Costas Busch - LSU a, b q4 32 Initial State q0 Example a, b q5 a b

a b q0 a q1 b q2 b q3 a Costas Busch - LSU a, b q4 33 Set of Accepting States F Q Example F q4 a, b q5 a

b a b q0 a q1 b q2 b q3 a Costas Busch - LSU a, b q4 34 Transition Function : Q Q (q, x ) q q x

q Describes the result of a transition from state q with symbol x Costas Busch - LSU 35 Example: q0 , a q1 a, b q5 a b a b q0 a q1 b q2 b q3 a Costas Busch - LSU

a, b q4 36 q0 , b q5 a, b q5 a b a b q0 a q1 b q2 b q3 a Costas Busch - LSU a, b q4 37

q2 , b q3 a, b q5 a b a b q0 a q1 b q2 b q3 a Costas Busch - LSU a, b q4 38 Transition Table for

symbols states q0 q1 q2 q3 q4 q5 a q1 q5 q5 q4 q5 q5

b q5 q2 q3 q5 q5 q5 a, b q5 a b a b q0 a q1 b q2 b q3 a Costas Busch - LSU a, b

q4 39 Extended Transition Function * * : Q Q * (q,w ) q Describes the resulting state after scanning string w from stateq Costas Busch - LSU 40 Example:

* q0 , ab q2 a, b q5 a b a b q0 a q1 b q2 b q3 a Costas Busch - LSU a, b q4 41 * q0 , abbbaa q5

a, b q5 a b a b q0 a q1 b q2 b q3 a Costas Busch - LSU a, b q4 42 * q1,bba q4 a, b q5

a b a b q0 a q1 b q2 b q3 a Costas Busch - LSU a, b q4 43 Special case: for any state q * q, q Costas Busch - LSU 44

In general: * q,w q implies that there is a walk of transitions w 1 2 k q 1 k 2 q states may be repeated

q w Costas Busch - LSU q 45 Language Accepted by DFA Language accepted by DFA M : it is denoted as L M and contains all the strings accepted by M We also say that M recognizesL M Costas Busch - LSU 46

For a DFA M Q, , , q0 , F Language accepted by : M * * L M w : q0 , w F q0 w

Costas Busch - LSU q q F 47 Language rejected byM * : * L M w : q0 , w F q0

w Costas Busch - LSU q q F 48 More DFA Examples {a,b } a, b a, b q0

q0 L(M ) { } L(M ) Empty language * All strings Costas Busch - LSU 49 {a,b } a, b q0 a, b

q1 L( M ) { } Language of the empty string Costas Busch - LSU 50 {a,b } L M= { all strings with prefix ab } a, b q0 a q1 b

a q3 Costas Busch - LSU b q2 accept a, b 51 { all binary strings containing L M= substring 001 } 0,1 0 1

1 0 0 00 1 001 0 Costas Busch - LSU 52 L M = { all binary strings without substring 001 }

0 1 0,1 1 0 0 00 1 001

0 Costas Busch - LSU 53 L( M ) awa : w a, b * b a b q0 a

q2 q3 a b q1 a, b Costas Busch - LSU 54 Regular Languages Definition: A languageL 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 Costas Busch - LSU 55 Example regular languages: abba , ab, abba n {a b : n 0} awa : w a, b * { all strings in {a,b}* with prefixab }

{ all binary strings without substring 001 } * {x : x {1} and x is even} { } { } * {a, b} There exist DFAs that accept these languages (see previous slides). Costas Busch - LSU 56 here exist languages which are not Regular: n n

L{a b : n 0} ADDITION n m k {x y z : x 1 , y 1 , z 1 , n m k } There are no DFAs that accept these language (we will prove this later) Costas Busch - LSU 57