automata theory bcbcvbcbvcbbbbbbvcbcbvcbcbcbcvbcvbvcbcvbcvbcvbcvbcvbcvbcvbcvbcvbcbcb

elaine rich ppts bccv

1. Finite State Machines
Chapter 5

2. Languages and Machines

3. Regular Languages
Regular
Language
Regular Expression
Finite State
Machine
L
Accepts

4. There are two types of FSM
•Deterministic FSM (DFSM): in these machines there is
always exactly one move that can be made from each step;
this is determined by the current state and the next input
character.
•Nondeterministic FSM (NDFSM): in these machines there
may be at various points in the computation more than one
move from which the machine has to decide.

5. Definition of a DFSM
Mis a quintuple = (K, , , s, A), where:
Kis a finite set of states
is an alphabet
sKis the initial state
AKis the set of accepting states, and
is the transition function from
(K) to K
state input symbol state

6. Accepting by a DFSM
Informally, Maccepts a string wiff Mwinds up in some
element of Awhen it has finished reading w.
The language accepted by M, denoted L(M), is the set
of all strings accepted by M.

7. Configurations of DFSMs
A configurationof a DFSM Mis an element of:
K*
It captures the two things that can make a difference to
M’s future behavior:
• its current state
• the input that is still left to read.
The initial configurationof a DFSM M, on input w, is:
(s
M, w)

8. The Yields Relations
The yields-in-one-steprelation |-
M:
(q, w) |-
M(q', w') iff
• w= aw'for some symbol a, and
• (q, a) = q'
|-
M*is the reflexive, transitive closure of |-
M.

9. Computations Using FSMs
A computationby Mis a finite sequence of
configurations C
0, C
1, …, C
nfor some n0 such
that:
• C
0is an initial configuration,
• C
nis of the form (q, ), for some state qK
M,
• C
0|-
MC
1|-
MC
2|-
M… |-
MC
n.

10. Accepting and Rejecting
A DFSM Macceptsa string wiff:
(s, w) |-
M* (q, ), for some qA.
A DFSM Mrejectsa string wiff:
(s, w) |-
M* (q, ), for some qA
M.
The language accepted byM, denoted L(M), is the
set of all strings accepted by M.
Theorem:Every DFSM M, on input s, halts in |s|
steps.

11. An Example Computation
An FSM to accept odd integers:
even odd
even
q
0 q
1
odd
On input 235, the configurations are:
(q
0, 235) |-
M (q
0, 35)
|-
M
|-
M
Thus (q
0, 235) |-
M* (q
1, )

12. Regular Languages
A language is regulariff it is accepted by some
FSM.

13. A Very Simple Example
L= {w{a, b}* :
every ais immediately followed by a b}.

14. A Very Simple Example
L= {w{a, b}* :
every ais immediately followed by a b}.

15. Parity Checking
L= {w{0, 1}* : whas odd parity}.

16. Parity Checking
L= {w{0, 1}* : whas odd parity}.

17. No More Than One b
L= {w{a, b}* : every aregion in wis of even length}.

18. No More Than One b
L= {w{a, b}* : every aregion in wis of even length}.

19. Checking Consecutive Characters
L= {w{a, b}* :
no two consecutive characters are the same}.

20. Checking Consecutive Characters
L= {w{a, b}* :
no two consecutive characters are the same}.

21. Dead States
L=
{w{a, b}* : every aregion in wis of even length}

22. Dead States
L=
{w{a, b}* : every aregion in wis of even length}

23. Dead States
L=
{w{a, b}* : every bin wis surrounded by a’s}

24. The Language of Floating Point
Numbers is Regular
Example strings:
+3.0, 3.0, 0.3E1, 0.3E+1, -0.3E+1, -3E8
The language is accepted by the DFSM:

25. A Simple Communication Protocol

26. Controlling a Soccer-Playing Robot

27. A Simple Controller

28. Programming FSMs
Cluster strings that share a “future”.
Let L= {w{a, b}* : wcontains an even
number of a’s and an odd number of b’s}

29. Even a’s Odd b’s

30. Vowels in Alphabetical Order
L= {w{a-z}* : all five vowels, a, e, i, o, and u,
occur in win alphabetical order}.

31. Vowels in Alphabetical Order
L= {w{a-z}* : all five vowels, a, e, i, o, and u,
occur in win alphabetical order}.

32. Programming FSMs
L= {w{a, b}* : wdoes not contain the
substring aab}.

33. Programming FSMs
L= {w{a, b}* : wdoes not contain the substring
aab}.
Start with a machine for L:
How must it be changed?

34. A Building Security System
L= {event sequences such that the alarm
should sound}

35. FSMs Predate Computers
The Prague Orloj, originally built in 1410.

36. The Abacus

37. The Jacquard Loom
Invented in 1801.

38. Finite State Representations in
Software Engineering
A high-level state chart model of a digital watch.

39. Making the Model Hierarchical

40. The Missing Letter Language
Let = {a, b, c, d}.
Let L
Missing=
{w: there is a symbol a
inot appearing in w}.
Try to make a DFSM for L
Missing:

41. Definition of an NDFSM
M= (K, , , s, A), where:
Kis a finite set of states
is an alphabet
sKis the initial state
AKis the set of accepting states, and
is the transition relation. It is a finite subset of
(K({})) K

42. Accepting by an NDFSM
Maccepts a string wiff there exists some pathalong
which wdrives Mto some element of A.
The language accepted by M, denoted L(M), is the set
of all strings accepted by M.

43. Sources of Nondeterminism

44. Two approaches:
• Explore a search tree:
• Follow all paths in parallel
Analyzing Nondeterministic FSMs

45. Optional Substrings
L= {w{a, b}* : wis made up of an optional a
followed by aafollowed by zero or more b’s}.

46. Multiple Sublanguages
L= {w{a, b}* : w= abaor |w| is even}.

47. The Missing Letter Language
Let = {a, b, c, d}. Let L
Missing= {w: there is a
symbol a
inot appearing in w}

48. The Missing Letter Language

49. Pattern Matching
L= {w{a, b, c}* : x, y{a, b, c}* (w= xabcabby)}.
A DFSM:

50. Pattern Matching
L= {w{a, b, c}* : x, y{a, b, c}* (w= xabcabby)}.
An NDFSM:

51. Pattern Matching with NDFSMs
L= {w{a, b}* :
x, y{a, b}* : w= xaabbbyor
w= xabbaby}

52. Multiple Keywords
L= {w{a, b}* : x, y{a, b}*
((w= xabbaay) (w= xbabay))}.

53. Checking from the End
L= {w{a, b}* :
the fourth to the last character is a}

54. Checking from the End
L= {w{a, b}* :
the fourth to the last character is a}

55. Another Pattern Matching Example
L= {w{0, 1}* : wis the binary encoding of a
positive integer that is divisible by 16 or is
odd}

56. Another NDFSM
L
1= {w{a, b}*: aaoccurs in w}
L
2= {x{a, b}*: bboccurs in x}
L
3= {y: L
1or L
2}
M
1=
M
2=
M
3=

57. A “Real” Example

58. English Morphology

59. Analyzing Nondeterministic FSMs
Does this FSM accept:
baaba
Remember: we just have to find one accepting path.

60. Two approaches:
• Explore a search tree:
• Follow all paths in parallel
Analyzing Nondeterministic FSMs

61. Another Nondeterministic Example
b* (b(ac)cb(ab) (c))* b

62. Dealing with Transitions
eps(q) = {pK: (q, w) |-*
M(p, w)}.
eps(q) is the closure of {q} under the relation
{(p, r) : there is a transition (p, , r) }.
How shall we compute eps(q)?

63. An Algorithm to Compute eps(q)
result= {q}.
While there exists some presultand
some rresultand
some transition (p, , r) do:
Insert r into result.
Return result.
eps(q: state) =

64. An Example of eps
eps(q
0) =
eps(q
1) =
eps(q
2) =
eps(q
3) =

65. Simulating a NDFSM
ndfsmsimulate(M: NDFSM, w: string) =
1.current-state= eps(s).
2.While any input symbols in wremain to be read do:
1.c= get-next-symbol(w).
2.next-state= .
3.For each state qin current-statedo:
For each state psuch that (q, c, p) do:
next-state= next-stateeps(p).
4.current-state= next-state.
3.If current-statecontains any states in A, accept. Else
reject.

66. Nondeterministic and
Deterministic FSMs
Clearly: {Languages accepted by a DFSM} 
{Languages accepted by a NDFSM}
More interestingly:
Theorem:
For each NDFSM, there is an equivalent DFSM.

67. Nondeterministic and
Deterministic FSMs
Theorem:For each NDFSM, there is an
equivalent DFSM.
Proof:By construction:
Given a NDFSM M= (K, , , s, A),
we construct M' = (K', , ', s', A'), where
K'= P(K)
s'= eps(s)
A'= {QK: QA}
'(Q, a) = {eps(p): pKand
(q, a, p) for some qQ}

68. An Algorithm for Constructing the
Deterministic FSM
1. Compute the eps(q)’s.
2. Compute s'= eps(s).
3. Compute ‘.
4. Compute K'= a subset of P(K).
5. Compute A'= {QK': QA}.

69. The Algorithm ndfsmtodfsm
ndfsmtodfsm(M: NDFSM) =
1. For each state qin K
Mdo:
1.1 Compute eps(q).
2. s'= eps(s)
3. Compute ':
3.1 active-states= {s'}.
3.2 ' = .
3.3 While there exists some element Qof active-statesfor
which 'has not yet been computed do:
For each character cin 
Mdo:
new-state= .
For each state qin Q do:
For each state psuch that (q, c, p) do:
new-state= new-stateeps(p).
Add the transition (Q, c, new-state) to '.
If new-stateactive-statesthen insert it.
4. K'= active-states.
5. A'= {QK' : QA}.

70. An Example

71. The Number of States May Grow
Exponentially
No. of states after 0 chars: = 1
No. of new states after 1 char: = n
No. of new states after 2 chars: = n(n-1)/2
No. of new states after 3 chars: = n(n-1)(n-2)/6
Total number of states after nchars: 2
nn
n






1 n
n






2 n
n






3
|| = n

72. Another Hard Example
L= {w{a, b}* :
the fourth to the last character is a}

73. If the Original FSM is Deterministic
1. Compute the eps(q)s:
2. s'= eps(q0) =
3. Compute '
({q0}, odd, {q1}) ({q0}, even, {q0})
({q1}, odd, {q1}) ({q1}, even, {q0})
4.K'= {{q0}, {q1}}
5. A'= { {q1} }
M'= M
M

74. The Real Meaning of “Determinism”
Is Mdeterministic?
An FSM is deterministic, in the most general definition of
determinism, if, for each input and state, there is at most one
possible transition.
•DFSMs are always deterministic. Why?
•NDFSMs can be deterministic (even with -transitions and implicit
dead states), but the formalism allows nondeterminism, in general.
•Determinism implies uniquely defined machine behavior.
Let M=

75. Deterministic FSMs as Algorithms
L= {w{a, b}* : wcontains no more than one b}:

76. Deterministic FSMs as Algorithms
until accept or reject do:
S:s= get-next-symbol
if s= end-of-file then accept
else if s= a then go to S
else if s= b then go to T
T: s= get-next-symbol
if s= end-of-file then accept
else if s= a then go to T
else if s= b then reject
end

77. Deterministic FSMs as Algorithms
until accept or reject do:
S:s= get-next-symbol
if s= end-of-file then accept
else if s= a then go to S
else if s= b then go to T
T: s= get-next-symbol
if s= end-of-file then accept
else if s= a then go to T
else if s= b then reject
end
Length of Program: |K| (|| + 2)
Time required to analyze string w: O(|w| ||)
We have to write new code for every new FSM.

78. A Deterministic FSM Interpreter
dfsmsimulate(M: DFSM, w: string) =
1. st= s.
2. Repeat
2.1 c= get-next-symbol(w).
2.2 If cend-of-file then
2.2.1 st= (st, c).
until c= end-of-file.
3. If stAthen accept else reject.
Input: aabaa

79. Nondeterministic FSMs as
Algorithms
Real computers are deterministic, so we have three choices
if we want to execute a NDFSM:
1. Convert the NDFSM to a deterministic one:
•Conversion can take time and space 2
|K|
.
•Time to analyze string w: O(|w|)
2. Simulate the behavior of the nondeterministic one by
constructing sets of states "on the fly" during execution
•No conversion cost
•Time to analyze string w: O(|w| |K|
2
)
3. Do a depth-first search of all paths through the
nondeterministic machine.

80. A NDFSM Interpreter
ndfsmsimulate(M = (K, , , s, A): NDFSM, w: string) =
1. Declare the set st.
2. Declare the set st1.
3.st= eps(s).
4. Repeat
4.1c= get-next-symbol(w).
4.2 If c end-of-file then do
4.2.1st1= .
4.2.2 For all qstdo
4.2.2.1 For all r(q, c) do
4.2.2.1.1 st1= st1eps(r).
4.2.3st= st1.
4.2.4 If st= then exit.
until c= end-of-file.
6. If stAthen accept else reject.