# 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

## Recently Viewed Presentations

• Klaus . Riegel - Interpretation of Development . What does Riegel suggest about our development in adulthood? What are the four interrelated internal and external dimensions of development? When does development occur? How is this related to systems theory? Group...
• 24- Terrorism: Is the use of violence or the threat of violence to obtain political demands. 25-Theft: Is the crime of stealing 26-Treason: Is the crime of betraying your own country by helping its enemies. 27-Trespassing: Is entering privetly owned...
• Matthew 5:9 "Blessed are the peacemakers, for they will be called children of God." Colossians 1:19-20 "God was pleased to have all his fullness dwell in him, and through him to reconcile to himself all things, whether things on earth...
• Längdsektionen. Har som vanligt arrangerat Vinterspelen och Njurunda Runt. Fina resultat av unga åkare som Annika Westergren, Marcus Brugge, Sofia Andersson, Sven Olsson och Anders Persson. Fotbollen. Har bedrivits inom A-,B-, Juniorer och ungdomslag.
• Web Services API - Real-time data exchange . EIB Workbook File transfer. Data sent from JDXpert to Workday. Data sent from Workday to JDXpert . EIB format is natively supported in Workday and allows for complex data structures to be...
• "If you're going to wear your undies on your head, please get a clean pair." Mother's Day 2014. THE TRUTH . WILL SET YOU FREE. John 8:31-32 ...
• I won't allow it." She did not answer, only fought him silently, twisting like a cat and showing her teeth. Parrot → a symbol of her identity Animalistic behavior demonstrated → great contrast to Mr. Mason, who acts as a...
• Early Childhood Thought: Islands of Competence The Development of Children (5th ed.) Cole, Cole & Lightfoot Chapter 9 Early Childhood (age 2-6) Typical pattern of thinking in preschool years Mixture of sound logic and magical thinking Insight and ignorance The...