Assignment - ABCBA Machines and
Their Traces
|
Shown
below are graphical representations of two machines. In these
representations, the ovals represent control states of the machine;
the first letter in the sequence of symbols that appear on the
arrows refers to an element of the input vocabulary; the '/ '
separates this symbol from symbols that represent the actions
taken on this transition; and the arrow points to the control
state that results when the transition is taken.
The
first machine is a Finite State Machine and the action
is represented by the single symbol 'R' which refers to the movement
of the read head to the right. The Finite State Machine depicted
below is one possible way in which to realize a Finite State
Machine that accepts the "language" L1. The
formula below this graph characterizes the language L1. The
rules or "Tuples" that define this Finite State Machine
are shown on the left below.
The first two columns
of the table list the condition for the rule and consist of the
pair <current control state, current symbol under read head>.
The last two columns specify the action component of the rule
and consists of the pair <move right (R), new current control
state>. Note that since this is a Finite State Machine the
movement is always R. The third column is "grayed out"
to indicate that this column is irrelevant in the definition
of this machine.
|
Tuples
| current control state |
symbol
under read head |
new symbol |
action |
new
control state |
| start |
A |
A |
R |
q_a1 |
| q_a1 |
A |
A |
R |
q_a1 |
| q_a1 |
B |
B |
R |
q_b1 |
| q_b1 |
B |
B |
R |
q_b1 |
| q_b1 |
C |
C |
R |
q_c1 |
| q_c1 |
C |
C |
R |
q_c1 |
| q_c1 |
B |
B |
R |
q_b2 |
| q_b2 |
B |
B |
R |
q_b2 |
| q_b2 |
A |
A |
R |
q_a2 |
| q_a2 |
A |
A |
R |
q_a2 |
| q_a2 |
# |
# |
R |
halt |
|
|
 |
| This third column is included here because
the traces for this machine were created using a "Turing
Machine" where the rules were defined as quintuples. The
third element of the quintuple specifies whether or not the symbol
that has been read is to be altered. In order to simulate a Finite
State Machine, the symbols were never altered. However, this
component of the rule will appear in the traces below. And, of
course, it will be used when a Turing Machine is specified. |
| Shown
below are traces of this machine accepting the strings AAABBCCCBAA## and
ABCBA##.
In these traces the number on the left indicates the step in
the trace. The next entry represents the current content of the
tape. The symbol that is underlined and shown in red indicates
the position of the read head. And, the final column reproduces
the rule that was applied at that step in the trace. |
| |
| Testing
String AAABBCCCBAA## |
01 - AAABBCCCBAA##
- start A A R q_a1
02 - AAABBCCCBAA## - q_a1 A A R q_a1
03 - AAABBCCCBAA## - q_a1 A A R q_a1
04 - AAABBCCCBAA## - q_a1 B B R q_b1
05 - AAABBCCCBAA## - q_b1 B B R q_b1
06 - AAABBCCCBAA## - q_b1 C C R q_c1
07 - AAABBCCCBAA## - q_c1 C C R q_c1
08 - AAABBCCCBAA## - q_c1 C C R q_c1
09 - AAABBCCCBAA## - q_c1 B B R q_b2
10 - AAABBCCCBAA## - q_b2 A A R q_a2
11 - AAABBCCCBAA## - q_a2 A A R q_a2
12 - AAABBCCCBAA## - q_a2 # # R halt
13 - AAABBCCCBAA## |
| AAABBCCCBAA##
was ACCEPTED. |
|
|
|
| |
| Testing String ABCBA## |
01 - ABCBA## - start
A A R q_a1
02 - ABCBA## - q_a1 B B R q_b1
03 - ABCBA## - q_b1 C C R q_c1
04 - ABCBA## - q_c1 B B R q_b2
05 - ABCBA## - q_b2 A A R q_a2
06 - ABCBA## - q_a2 # # R halt
70 - ABCBA## |
| ABCBA##
was ACCEPTED |
|
|
The
trace shown below and left records the result when a string,
ABBCAAB##, that
is not in L1
is provided as input.
In this case the string is processed until an A
is encountered after a C. This is
the first point where the string deviates from the regularities
that define L1. At this point there is no rule that
applies and the machine hangs.
|
| |
| Testing String ABBCAAB## |
01 - ABBCAAB##
- start A A R q_a1
02 - ABBCAAB## - q_a1 B B R q_b1
03 - ABBCAAB## - q_b1 B B R q_b1
04 - ABBCAAB## - q_b1 C C R q_c1
05 - ABBCAAB## |
| ABBCAAB##
was REJECTED. |
|
|
|
| |
| Testing String #### |
| 01 - ####
- |
| ####
was REJECTED. |
|
|
Finally,
the trace above shows that the machine appropriately rejects
the empty string as an element of L1.
|
|
Next
we turn to a Turing Machine that defines one possible
way in which to realize a machine that accepts the "language"
L2. This machine is depicted below. The rules
or "Tuples" that define this Turing Machine are shown
on the left below.
As
in the above Finite State Machine, the first two columns of the
table list the condition for the rule and consist of the pair
<current control state, current
symbol under read head>. However,
in this case the remaining three columns specify the action component
of the rule and consists of the triple <new
symbol, action, new current control state>.
One can think about the problem
of accepting the strings of L2 as
consisting of three components or subproblems which can be informally
characterized as:
- ensuring that all A's
are at the beginning and end of the string and each contains
n A's (this subproblem is shown in yellow
in the figure below);
- ensuring that the first sequence
of B's
occurs after the initial sequence of A's and the second sequence of B's
occurs before the second sequence of A's and each string of B's contains
m B's (this subproblem is shown in blue
in the figure below);;
- and, ensuring that the sequence
of C's occurs after the first sequence of
B's
and before the second sequence of B's and that the string of C's is an even number (this subproblem
is shown in green in the figure below);.
|
Tuples
| current control state |
symbol under read head |
new symbol |
action |
new control state |
| start |
A |
# |
R |
q_arb |
| q_arb |
A |
A |
R |
q_arb |
| q_arb |
B |
B |
R |
q_arb |
|
q_arb |
C |
C |
R |
q_arb |
| q_arb |
# |
# |
L |
q_are |
| q_are |
A |
# |
L |
q_alb |
| q_alb |
A |
A |
L |
q_alb |
| q_alb |
B |
B |
L |
q_alb |
| q_alb |
C |
C |
L |
q_alb |
| q_alb |
# |
# |
R |
q_ale |
| q_ale |
A |
# |
R |
q_arb |
| q_ale |
B |
# |
R |
q_brb |
| q_brb |
B |
B |
R |
q_brb |
| q_brb |
C |
C |
R |
q_brb |
| q_brb |
# |
# |
L |
q_bre |
| q_bre |
B |
# |
L |
q_blb |
| q_blb |
B |
B |
L |
q_blb |
| q_blb |
C |
C |
L |
q_blb |
| q_blb |
# |
# |
R |
q_ble |
| q_ble |
B |
# |
R |
q_brb |
| q_ble |
C |
# |
R |
q_crb |
| q_crb |
C |
C |
R |
q_crb |
| q_crb |
# |
# |
L |
q_cre |
| q_cre |
C |
# |
L |
q_clb |
| q_clb |
C |
C |
L |
q_clb |
| q_clb |
# |
# |
R |
q_cle |
| q_cle |
C |
# |
R |
q_crb |
| q_cle |
# |
# |
S |
halt |
|
|
 |
| By
controlling the order in which these subproblems are solved,
this Turing Machine is able to solve the problem in a rather
simple fashion. The traces below further exemplify the operation
of this machine. |
| |
| Testing String ABCCBA## |
01 - ABCCBA##
- start A # R q_arb
02 - #BCCBA## - q_arb B B R q_arb
03 - #BCCBA## - q_arb C C R q_arb
04 - #BCCBA## - q_arb C C R q_arb
05 - #BCCBA## - q_arb B B R q_arb
06 - #BCCBA## - q_arb A A R q_arb
07 - #BCCBA## - q_arb # # L q_are
08 - #BCCBA## - q_are A # L q_alb
09 - #BCCB### - q_alb B B L q_alb
10 - #BCCB### - q_alb C C L q_alb
11 - #BCCB### - q_alb C C L q_alb
12 - #BCCB### - q_alb B B L q_alb
13 - #BCCB### - q_alb # # R q_ale
14 - #BCCB### - q_ale B # R q_brb
15 - ##CCB### - q_brb C C R q_brb
16 - ##CCB### - q_brb C C R q_brb
17 - ##CCB### - q_brb B B R q_brb
18 - ##CCB### - q_brb # # L q_bre
19 - ##CCB### - q_bre B # L q_blb
20 - ##CC#### - q_blb C C L q_blb
21 - ##CC#### - q_blb C C L q_blb
22 - ##CC#### - q_blb # # R q_ble
23 - ##CC#### - q_ble C # R q_crb
24 - ###C#### - q_crb C C R q_crb
25 - ###C#### - q_crb # # L q_cre
26 - ###C#### - q_cre C # L q_clb
27 - ######## - q_clb # # R q_cle
28 - ######## - q_cle # # S halt |
| ABCCBA## was ACCEPTED. |
|
|
|
 |
 |
ABCBA##
Trace |
 |
AACCBBAA##
Trace |
AABBBCCBBBAA##
Trace |
|
