Transcript class1

CSSE 350
Automata, Formal Languages, and
Computability
1
Mathematical Preliminaries and Background
•
Sets
•
Relations
•
Functions
•
Logic
•
Graphs
•
Trees
•
Proof Techniques
•
Languages and Strings
•
Automaton
2
Sets
3
SETS
A set is a collection of elements, having a property that
characterizes those elements.
A  {1, 2, 3}
B  {train, bus, bicycle, airplane}
We write Belongs To and Does not Belong To as:
1 A
ship  B
4
Set Representations
• One way is to enumerate the elements completely. All the
elements belonging to the set are explicitly given.
–
For example, A = {1,2,3,4,5}
• Alternate way is to give the properties that characterize
the elements of the set.
–
For example, B = {x | x is a positive integer less than or equal to
5}
– Or B = {x : x is a positive integer less than or equal to 5}
• Ellipses may be used in the set specification if the
meaning is clear. For example, C = { a, b, …, z}, which
stands for all the lower-case letters of the English
alphabet
5
Set Representations
C = { a, b, c, d, e, f, g, h, i, j, k }
C = { a, b, …, k }
finite set
S = { 2, 4, 6, … }
infinite set
S = { j : j > 0, and j = 2k for some k>0 }
S = { j : j is nonnegative and even }
6
A = { 1, 2, 3, 4, 5 }
U
A
6
1
7
10
Universal Set:
2
4
8
3
5
9
all possible elements
U = { 1 , … , 10 }
7
Set Operations
A = { 1, 2, 3 }
B = { 2, 3, 4, 5}
B
A
• Union
A U B = { 1, 2, 3, 4, 5 }
2
1
3
4
5
• Intersection
U
A
B = { 2, 3 }
2
3
• Difference
A-B={1}
B - A = { 4, 5 }
1
Venn diagrams
8
• Complement
Universal set = {1, …, 7}
A = { 1, 2, 3 }
4
A = { 4, 5, 6, 7}
A
1
5
A
2
6
3
7
A=A
9
{ even integers } = { odd integers }
Integers
1
odd
2
3
even
0
4
5
6
7
10
DeMorgan’s Laws
U
A
U
AUB=A
B
B=AUB
11
Empty, Null Set:
={}
SU
=S
S
=
U
S-
= Universal Set
=S
-S=
12
Subset
A = { 1, 2, 3}
B = { 1, 2, 3, 4, 5 }
B
U
Proper Subset: A
U
A
B
B
A
13
Disjoint Sets
A = { 1, 2, 3 }
A
U
A
B = { 5, 6}
B=
B
14
Set Cardinality
• For finite sets
A = { 2, 5, 7 }
|A| = 3
(set size)
15
Powersets
A powerset is a set of sets
S = { a, b, c }
Powerset of S = the set of all the subsets of S
2S = {
, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }
Observation: | 2S | = 2|S|
( 8 = 23 )
16
Cartesian Product
A = { 2, 4 }
B = { 2, 3, 5 }
A X B = { (2, 2), (2, 3), (2, 5), ( 4, 2), (4, 3), (4, 5) }
|A X B| = |A| |B|
Generalizes to more than two sets
AXBX…XZ
17
Set Identities
A, B, C represent arbitrary sets and ø is the empty set and
U is the Universal Set.
The Commutative laws:
AB=BA
AB=BA
The Associative laws:
A  (B  C) = (A  B)  C
A  (B  C) = (A  B)  C
The Distributive laws:
A  (B  C) = (A  B)  (A  C)
A  (B  C) = (A  B)  (A  C)
18
The Idempotent laws:
AA=A
AA=A
The Absorptive laws:
A  (A  B) = A
A  (A  B) = A
The De Morgan laws:
(A  B)' = A'  B'
(A  B)' = A'  B'
Other laws involving Complements:
( A' )' = A
A  A' = ø
A  A' = U
19
Other laws involving the empty set
Aø=A
Aø=ø
Other laws involving the Universal Set:
AU=U
AU=A
20
RELATIONS
21
Relations
Let A and B be sets. A binary relation from A into B is any
subset of the Cartesian product A  B.
For example: let A = {2, 3, 5, 6}, and B = {1, 2, 3, 4, 5, 6, 7,
8, 9, 10, 11, 12, 13, 14, 15}, and a relation R from A into B
by (a, b) R if and only if 2a = b
So, R = {(2, 4), (3, 6), (5, 10), (6, 12)}.
22
A typical element in R is an ordered pair (x, y). In some
cases R can be described by actually listing the pairs
which are in R, as in the previous example. This may not be
convenient if R is relatively large.
Other notations are used depending on the past practice.
Consider the following relation on real numbers.
R = {(x, y) | y is the square of x} and S = {(x, y) | x <= y}.
R could be more naturally expressed as R(x) = x2 or R(x) =y
where y = x2.
23
RELATIONS
R = {(x1, y1), (x2, y2), (x3, y3), …}
xi R yi
e. g. if R = ‘>’: 2 > 1, 3 > 2, 3 > 1
24
Relation on a Set
A relation from a set A into itself is called a relation on A.
For example, let A = {1, 2, 3, 4, 5, 6}, and a relation R from A
to A itself by (a, b) R if and only if a is a divisor of b
So, R = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 4),
(2, 6), (3, 3), (3, 6), (4, 4), (5, 5), (6, 6)}.
Let A be a set of people and let P = {(a, b) | a  A  b  A 
a is a child of b}. Then P is a relation on A which we might
call a parent-child relation.
25
Composition
Let R be a relation from a set A into set B, and S be a
relation from set B into set C. The composition of R and S,
written as RS, is the set of pairs of the form (a, c)  A 
C, where (a, c)  RS if and only if there exists b B such
that (a, b)  R and (b, c)  S.
For example PP, where P is the parent-child relation given, is
the composition of P with itself and it is a relation which
we know as grandparent-grandchild relation.
26
Properties of Relations
Assume R is a relation on set A; in other words, R  A  A.
Let us write a R b to denote (a, b) R.
1. Reflexive: R is reflexive if for every a  A, a R a.
2. Symmetric: R is symmetric if for every a and b in A, if
aRb, then bRa.
3. Transitive: R is transitive if for every a, b and c in A, if
aRb and bRc, then aRc.
4. Equivalence: R is an equivalence relation on A if R is
reflexive, symmetric and transitive.
For example, the equality relation (=) on a set of numbers
such as {1, 2, 3} is an equivalence relation.
27
Equivalence Relations
• Reflexive:
xRx
• Symmetric:
xRy
• Transitive:
x R y and y R z
yRx
xRz
Example: R = ‘=‘
•x=x
•x=y
• x = y and y = z
y=x
x=z
28
FUNCTIONS
29
Functions
A function is something that associates each element of a
set with an element of another set (which may or may not
be the same as the first set).
Or a function is a rule that assigns to elements of one set a
unique element of another set.
For example, a social security number uniquely identifies a
person, in this case, to each member of the set of social
security number, some member of the set of person is
assigned.
30
FUNCTIONS
domain
4
A
1
2
5
If A = domain
range
B
f(1) = a
a
b
3
c
f : A -> B
then f is a total function
otherwise f is a partial function
31
Growth Rates of Functions
Let f(n) and g(n) to be two functions whose domain is a
subset of the positive integers
If there exists a positive constant c such that for all
sufficiently large n
f(n) ≤ cg(n)
f has the order at most g
f(n) = O(g(n))
cg(n)
f(n)
32
If there exists a positive constant c such that for all
sufficiently large n
f(n)  cg(n)
f has the order at least g
f(n) =  (g(n))
f(n)
cg(n)
33
If there exist positive constant c1 and c2, such that for all
sufficiently large n
c1g(n) ≤ f(n) ≤ c2g(n)
f and g have the same order of magnitude
f(n) =  (g(n))
f(n)
c2g(n)
c1g(n)
34
Examples
Example 1: 2n is Θ(n)
f(n) = 2n, g(n) = n
For all integers n ≥ 0, 2n ≤ 2n, which is f(n) ≤ 2g(n); so
constant c ≥ 2 suffices for the definition of O.
For all integers n ≥ 0, 2n ≥ n, which is f(n) ≥ 1g(n); so any 0
< c ≤ 2 suffices for the definition of Ω.
Since 2n is both O(n) and Ω(n), it is Θ(n).
35
Example 2: n is O(n2) but not Ω(n2)
f(n) = n, g(n) = n2
For all integers n ≥ 0, n ≤ n2; which is f(n) ≤ 1g(n); so
constant c ≥ 1 suffices for the definition of O.
However, n cannot be Ω(n2) since no matter how small c>0
is chosen, for all n > 1/c, n = c(1/c)n < cnn = cn2.
36
Logic
Propositional Logic & Predicate
Logic
37
Propositional Logic
Proposition: a declarative statement having a
specific truth-value, true or false.
For example:
8 is an even number.
4 is a negative number.
 True
 False
38
Two or more propositions can be combined together to make
compound propositions with the help of logical
connectives.
For example: above two propositions can be used to make
a compound proposition using any of the logical
connectives.
8 is an even number AND 4 is a negative number.
 False
8 is an even number OR 4 is a negative number.
True
For the first compound proposition to be true both the
propositions have to be true as the connective is AND. As
OR is the connective for the second one, if either of the
propositions is true, the truth value of the compound
proposition is true.
39
logical Connectives
Conjunction: The compound proposition truth-value is true
if and only if all the constituent propositions hold true.
It is represented as " ^ ". Truth table for two
individual propositions p and q with conjunction is given
below.
p
q
p q
T
T
T
T
F
F
F
T
F
F
F
F
40
Disjunction: This is logical "or" read as either true value
of the individual propositions. Truth table is given
below.
p
q
pVq
T
T
T
T
F
T
F
T
T
F
F
F
41
Negation: This is the logical "negation" and it is expressed
by as ¬p for "not p". Truth table is given below.
p
¬p
T
F
F
T
42
Conditional: This is used to define as "a proposition holds
true if another proposition is true" i.e. p  q is read as
"if p, then q". Truth table is given below.
p
q
pq
T
T
T
T
F
F
F
T
T
F
F
T
43
Biconditional: A proposition (p  q) ^ (q  p) can be
abbreviated using biconditional conjunction as p  q
and is read as "if p then q, and if q then p".
Tautology: A compound proposition, which is true in every
case. E.g., p V ¬ p
Contradiction: This is the opposite of tautology, which is
false in every case. E.g., p  ¬ p
44
Identities
¬ (P  Q)  (¬ P  ¬Q) ----- DeMorgan's Law
¬ (P  Q)  (¬ P  ¬ Q) ----- DeMorgan's Law
(P  Q)  (¬ P  Q) ----- implication
[(P  Q)  R]  [P  (Q  R)] ----- exportation
(P  Q)  (¬ Q  ¬P) ----- contrapositive
45
Implications
[(P  Q)  ¬Q]  P ----- modus tollens
[(P  Q)  (R  S)]  [(P  R)  (Q  S)]
[(P  Q)  (Q  R)]  (P  R)
46
Predicate Logic
The propositional logic is not powerful enough to represent all types of
assertions. For example, the statement: x is a non-zero integer,
where x is a variable, is not a proposition because you can not tell
whether it is true or false unless you know the value of x. Thus the
propositional logic can not deal with such sentences.
The predicate logic is one of the extensions of propositional logic and it
is fundamental to most other types of logic. Central to the predicate
logic are the concepts of predicate and quantifier.
A predicate is a feature of language which you can use to make a
statement about something, e.g. to attribute a property to that thing.
If you say "Peter is tall", then you have applied to Peter the
predicate "is tall". We also might say that you have predicated
tallness of Peter or attributed tallness to Peter.
47
A predicate is a template involving a verb that describes a property of
objects, or a relationship among objects represented by the
variables. For example, the sentences:
The flower is red.
The sweater is red.
The frame is red.
All these sentences come from the template "is red" by placing an
appropriate noun/noun phrase in front of it. The phrase "is red" is a
predicate and it describes the property of being red. Predicates are
often given a name.
For example any of "is_red", "Red" or "R" can be used to represent the
predicate "is red" among others. We can adopt Red as the name for
the predicate “is_red". Sentences that assert an object is red can be
represented as "Red(x)", where x represents an arbitrary object.
Red(x) reads as "x is red".
48
A predicate with variables, called atomic formula,
can be made a proposition by applying one of the
following two operations to each of its variables:
assign a value to the variable
quantify the variable using a quantifier
For example, x > 1 becomes 3 > 1 if 3 is assigned to
x, and it becomes a true statement, and it
becomes a proposition.
In general, a quantification is performed on
formulas of predicate logic (called wff), such as
x > 1 or P(x), by using quantifiers on variables.
49
There are two types of quantifiers:
universal quantifier
existential quantifier
The universal quantifier turns, for example, the statement x
> 1 to "for every object x in the universe, x > 1", which is
expressed as " x x > 1". This new statement is true or
false in the universe of discourse. Hence it is a
proposition once the universe is specified.
Similarly the existential quantifier turns, for example, the
statement x > 1 to "for some object x in the universe, x >
1", which is expressed as " x x > 1." Again, it is true or
false in the universe of discourse, and hence it is a
proposition once the universe is specified.
50
The universe of discourse, also called universe, is the set of
objects of interest. The propositions in the predicate
logic are statements on objects of a universe.
The universe is thus the domain of the (individual) variables.
It can be:
the set of real numbers
the set of integers
the set of all cars on a parking lot
the set of all students in a classroom etc.
The universe is often left implicit in practice. But it should
be obvious from the context
51
Predicate logic is more powerful than propositional logic. It
allows one to reason about properties and relationships of
individual objects. In predicate logic, one can use some
additional inference rules, as well as those for
propositional logic such as the equivalences, implications
and inference rules.
Predicate logic permits reasoning about the propositional
connectives and also about quantification ("all" or "some").
A classic, if elementary, example of what can be done with
the predicate logic is the inference from the premises:
All men are mortal.
Socrates is a man.
to the conclusion
Socrates is mortal
52
Important Inference Rules of Predicate
Logic
First there is the following rule concerning the negation of
quantified statement which is very useful:
¬x P(x) x ¬P(x)
Next there is the following set of rules on quantifiers and
connectives:
x [P(x)  Q(x)]  [x P(x)  x Q(x)]
[x P(x)  x Q(x)]   x [P(x)  Q(x)]
x [P(x)  Q(x)] [x P(x)  x Q(x)]
x [P(x)  Q(x)] [x P(x)  x Q(x)]
53
GRAPHS
54
GRAPHS
A directed graph
e
node
b
d
a
c
• Nodes (Vertices)
V = { a, b, c, d, e }
• Edges
E = { (a,b), (b,c), (b,e),(c,a), (c,e), (d,c), (e,b), (e,d) }
55
Labeled Graph
2
6
a
b
1
5
3
e
6
2
d
c
56
Walk
e
b
d
a
c
Walk is a sequence of adjacent edges
(e, d), (d, c), (c, a)
57
Path
e
b
d
a
c
Path is a walk where no edge is repeated
Simple path: no node is repeated
58
Cycle
base
a
3
2
e
b
1
d
c
Cycle: a walk from a node (base) to itself
Simple cycle: only the base node is repeated
59
Euler Tour
8
b
4
a
7
3
6
5
base
e
1
2
d
c
A cycle that contains each edge once
60
Hamiltonian Cycle
5
b
4
a
3
base
e
1
2
d
c
A simple cycle that contains all nodes
61
Finding All Simple Paths
e
b
d
a
c
origin
62
Step 1
e
b
d
a
c
(c, a)
origin
(c, e)
63
Step 2
e
b
d
a
(c, a)
(c, a), (a, b)
c
origin
(c, e)
(c, e), (e, b)
(c, e), (e, d)
64
Step 3
e
b
d
a
(c, a)
(c, a), (a, b)
c
origin
(c, a), (a, b), (b, e)
(c, e)
(c, e), (e, b)
(c, e), (e, d)
65
Step 4
e
b
(c, a)
d
a
(c, a), (a, b)
(c, a), (a, b), (b, e)
c
origin
(c, a), (a, b), (b, e), (e,d)
(c, e)
(c, e), (e, b)
(c, e), (e, d)
66
Trees
67
root
Trees
parent
leaf
child
Trees have no cycles
68
root
Level 0
Level 1
Height 3
leaf
Level 2
Level 3
69
Binary Trees
70
PROOF TECHNIQUES
71
PROOF TECHNIQUES
• Proof by induction
• Proof by contradiction
72
Induction
We have statements P1, P2, P3, …
If we know
• for some b that P1, P2, …, Pb are true
• for any k >= b that
P1, P2, …, Pk imply Pk+1
Then
Every Pi is true
73
Proof by Induction
• Inductive basis
Find P1, P2, …, Pb which are true
• Inductive hypothesis
Let’s assume P1, P2, …, Pk are true,
for any k >= b
• Inductive step
Show that Pk+1 is true
74
Example
Theorem: A binary tree of height n
has at most 2n leaves.
Proof by induction:
let L(i) be the maximum number of
leaves of any subtree at height i
75
We want to show: L(i) <= 2i
• Inductive basis
L(0) = 1
(the root node)
• Inductive hypothesis
Let’s assume L(i) <= 2i for all i = 0, 1, …, k
• Induction step
we need to show that L(k + 1) <= 2k+1
76
Induction Step
height
k
k+1
From Inductive hypothesis: L(k) <= 2k
77
Induction Step
height
k
L(k) <= 2k
k+1
L(k+1) <= 2 * L(k) <= 2 * 2k = 2k+1
(we add at most two nodes for every leaf of level k)
78
Remark
Recursion is another thing
Example of recursive function:
f(n) = f(n-1) + f(n-2)
f(0) = 1, f(1) = 1
79
Proof by Contradiction
We want to prove that a statement P is true
• we assume that P is false
• then we arrive at an incorrect conclusion
• therefore, statement P must be true
80
Example
Theorem:
2
is not rational
Proof:
Assume by contradiction that it is rational
2
= n/m
n and m have no common factors
We will show that this is impossible
81
2
= n/m
Therefore,
2 m2 = 4k2
n2
2 m 2 = n2
is even
m2 = 2k2
n is even
n=2k
m is even
m=2p
Thus, m and n have common factor 2
Contradiction!
82
Languages and Strings
83
A language is a set of strings
String: A sequence of letters
Examples: “cat”, “dog”, “house”, …
Defined over an alphabet:
  a, b, c,, z
84
Alphabets and Strings
We will use small alphabets:
  a, b
Strings
a
ab
abba
baba
aaabbbaabab
u  ab
v  bbbaaa
w  abba
85
String Operations
w  a1a2 an
abba
bbbaaa
v  b1b2 bm
Concatenation
wv  a1a2  anb1b2 bm
abbabbbaaa
86
w  a1a2  an
ababaaabbb
Reverse
w  an  a2 a1
R
bbbaaababa
87
Concatenation and Reverse of Strings
Theorem: If w and x are strings, then (w x)R = xR wR.
Example:
(nametag)R = (tag)R (name)R = gateman
88
Concatenation and Reverse of Strings
Proof: By induction on |x|:
|x| = 0: Then x = , and (wx)R = (w )R = (w)R =  wR = R wR = xR wR.
n  0 (((|x| = n)  ((w x)R = xR wR)) 
((|x| = n + 1)  ((w x)R = xR wR))):
Consider any string x, where |x| = n + 1. Then x = u a for some
character a and |u| = n. So:
(w x)R = (w (u a))R
= ((w u) a)R
= a (w u)R
= a (uR wR)
= (a uR) wR
= (ua)R wR
= x R wR
rewrite x as ua
associativity of concatenation
definition of reversal
induction hypothesis
associativity of concatenation
definition of reversal
rewrite ua as x
89
String Length
w  a1a2  an
Length:
w n
Examples:
abba  4
aa  2
a 1
90
Length of Concatenation
uv  u  v
Example:
u  aab, u  3
v  abaab, v  5
uv  aababaab  8
uv  u  v  3  5  8
91
Empty String
A string with no letters:
Observations:

 0
w  w  w
abba  abba  abba
92
Substring
Substring of string:
a subsequence of consecutive characters
String
Substring
abbab
abbab
abbab
abbab
ab
abba
b
bbab
93
Prefix and Suffix
abbab
Prefixes

a
ab
abb
abba
abbab
Suffixes
abbab
bbab
bab
ab
b
w  uv
prefix
suffix

94
Another Operation (Replication)
w  ww

w




n
n
Example:
Definition:
abba   abbaabba
2
w 
0
abba   
0
95
The * Operation
 * : the set of all possible strings from
alphabet 
  a, b
*   , a, b, aa, ab, ba, bb, aaa, aab,
96
The + Operation
 : the set of all possible strings from

alphabet  except 
  a, b
*   , a, b, aa, ab, ba, bb, aaa, aab,

   * 

  a, b, aa, ab, ba, bb, aaa, aab,
97
Languages
A language is any subset of
*
Example:
  a, b
*   , a, b, aa, ab, ba, bb, aaa,
Languages:

a, aa, aab
{ , abba, baba, aa, ab, aaaaaa}
98
Note that:
Sets
  { }  {}
Set size
{}    0
Set size
{}  1
String length
 0
99
Another Example
An infinite language
L  {a b : n  0}
n n

ab
aabb
aaaaabbbbb
L
abb  L
100
Operations on Languages
The usual set operations
a, ab, aaaa  bb, ab  {a, ab, bb, aaaa}
a, ab, aaaa  bb, ab  {ab}
a, ab, aaaa  bb, ab  a, aaaa
Complement:
L   * L
a, ba   , b, aa, ab, bb, aaa,
101
Reverse
Definition:
Examples:
L  {w : w  L}
R
R
ab, aab, baba  ba, baa, abab
R
L  {a b : n  0}
n n
L  {b a : n  0}
R
n n
102
Concatenation
Definition:
Example:
L1L2  xy : x  L1, y  L2 
a, ab, bab, aa
 ab, aaa, abb, abaa, bab, baaa
103
Another Operation
Definition:
L 
LL

L
n
n
a, b  a, ba, ba, b 
aaa, aab, aba, abb, baa, bab, bba, bbb
3
0
Special case: L  
a , bba, aaa 0  
104
More Examples
L  {a b : n  0}
n n
L  {a b a b : n, m  0}
2
n n m m
2
aabbaaabbb L
105
Star-Closure (Kleene *)
Definition:
L*  L  L  L 
0
1
2
Example:
 ,

a, bb,



a, bb*  

aa
,
abb
,
bba
,
bbbb
,


aaa, aabb, abba, abbbb,
106
Positive Closure
Definition:

L  L  L 
 L * 
1
2
a, bb,


 
a, bb  aa, abb, bba, bbbb,

aaa, aabb, abba, abbbb,


107
Grammar
108
Grammar
Mathematically describe language
English: informal, inadequate
Set notations: limited
Grammar
English grammar describes whether a sentence is well-formed or not
<sentence>  <noun_phrase><predicate>
Then, what is noun_phrase, what is predicate?
<noun_phrase>  <article><noun>
<predicate>  <verb>
Basic idea of formal grammars:
Start from the top level concept
Reduce it to the irreducible building blocks
109
Grammar Definition
A grammar G is defined as a quadruple
G = (V, T, S, P)
V is a finite set of objects called variables
T is a finite set of objects called terminal symbols
S  V is a special symbol called the start variable
P is a finite set of productions
v and T are non-empty and disjoint
110
Production Rules
Heart of a grammar
Describe how the grammar transforms one string into another
Define a language associated with grammar
Production rules are of the form
x  y, where x  (V  T)+, y  (V  T)*
For example, given w = uxv, x  y,
then z = uyv, z is a new string
written as: w  z, means that w derives z or
z is derived from w
w1  w2  …  wn is the same as w*1
wn

111
Definition
Let G = (V, T, S, P) be a grammar. Then the set
*
L(G) = { w  T*
: S w}
is the language generated by G.
If w  L(G),
S  w1  w2  …  wn  w
is a derivation of the sentence w.
Strings S, w1, w2, …, wn are called sentential forms of the
derivation. All these strings may contain variables and terminals.
112
Automaton
113
Automaton
Input
S1
Control
Unit
S2
S4
S3
S5
Output
“Accept”
or
“Reject”
Storage
114
Automata
An abstract model of a digital computer
• Input mechanism
– Can read but not change an input file
• Input file
– Contains a string over a given alphabet
– Divided into cells, each cell holds one symbol
– The reading is from left to right, one symbol at a time
– Can sense the end of the input string
• Storage device
– Consist of an unlimited number of cells
– Each cell holds a symbol
– Can be read and changed
• Control unit
– Internal states
– Transition function (or next-state): gives the next state of the
control unit
• Current state
• Current input symbol
• Current information in the temporary storage
115
To Illustrate “State”
State: status, A state stores information about the past,
i.e. it reflects the input changes from the system start to
the present moment
Example: a robot
116
• Configuration
– A particular state of the control unit, input file, and temporary
storage
• Move
– The transition of the automaton from one configuration to the
next
• Deterministic automata
– Each move is uniquely determined by the current configuration
– If the internal state, the input, and the contents of the
temporary storage are known, the future behavior of the
automata can be predicted
• Nondeterministic automata
– At some point, the automata may have several moves
– A set of possible actions can be predicted
• Accepter
– An automata whose output response is either “yes” or “no”
117