Correct state row entries in the following Sequential machine?

  • Context: Undergrad 
  • Thread starter Thread starter elias001
  • Start date Start date
Click For Summary
SUMMARY

This discussion focuses on filling out the last state row entries for a sequential machine as described in the text "Arrows, Structures, and Functors: The Categorical Imperative" by Arbib and Manes. The state transitions are defined using the mappings ##\beta## and ##\delta##, where ##\beta:\{0,1\}\times D\to D## and ##\delta:\{0,1\}\times D\times D\times D\to \{0,1\}\times D##. The entries for states ##q_0## through ##q_5## are calculated based on the inputs and the defined transition rules, resulting in specific values for each state. The final state entries are confirmed as ##q_0=(0,0), q_1=(0,3), q_2=(0,1), q_3=(1,3), q_4=(0,0), q_5=(0,0)##.

PREREQUISITES
  • Understanding of sequential machines and state transitions
  • Familiarity with categorical mappings and functions
  • Knowledge of input-output relationships in automata theory
  • Basic proficiency in mathematical notation and logic
NEXT STEPS
  • Research the properties of sequential machines and their state transition diagrams
  • Study the application of categorical logic in automata theory
  • Explore the implications of input-output mappings in computational models
  • Learn about the implementation of state machines in programming languages
USEFUL FOR

This discussion is beneficial for computer scientists, mathematicians, and students studying automata theory or categorical logic, particularly those interested in the design and analysis of sequential machines.

elias001
Messages
389
Reaction score
30
TL;DR
I would like to know if my calculations for the state row entries for ##\{q_0,q_1,q_2,q_3,q_4,q_5\}## are correct.
The two screenshots below is taken from the text Arrows, Structures, and functiors The categorical Imperative By: Arbib and manes, pp 93-94

page 1
sequential machine 1.webp


page 2
sequential machine 2.webp


In the above two screenshots, I would like to fill out the last state row entries: ##q_0,q_1,q_2,q_3,q_4##

Let ##t=\{0,1,2,3,4,5\}, Y=D=\{0,1,2,3,4,5,6,7,8,9\}, Q=\{0,1\}\times D##

##q_t=q(t)=(c,cd)=(c,d), c\in \{0,1\}, cd=10c+d, q_t: cd\mapsto d\in D##

##\beta:\{0,1\}\times D\to D:cd\mapsto d##

##\delta:\{0,1\}\times D\times D\times D\to \{0,1\}\times D:(cd,x_1,x_2)\mapsto c'd'=c+x_1+x_2##

where ##x_1## denotes ##1##st input, and ##x_2## denotes ##2##nd input. For the ##\delta## map, we can let ##c'_{t+1}d_t'=c+x_{t1}+x_{t2},## where ##x_1=x_{t1}, x_2=x_{t2},##

Instead of ##c'##, we also can let ##c'=c'_{t+1}## and ##c_t=c\in \{0,1\}, c_{t+1}=1 \text{ if } c_t+x_{t1}+x_{t2}\geq 10, \text{ otherwise } c_{t+1}=0, \text{ also we let } d'=d_t.##

Then for:

##t=0, q_0=q(0)=(0,0,0),## so ##c_1=0, d_1=0, x_{01}=0, x_{02}=0, q_0=(0,0),##

##t=1, q_1=q(1)=(0,2,1)=(0,2+1), 0+2+4=3<10.## So ##c'_2=0,d'_1=3, x_{11}=2, x_{12}=1, q_1=(0,3),##

##t=2, q_2=q(2)=(0,7,4)=(0,7+4), 0+7+4=11>10.## So ##c'_3=1,d'_2=11-10=1, x_{21}=7, x_{22}=4,q_2=(0,1),##

##t=3, q_3=q(3)=(1,3,0)=(1,3+0), 1+3+0=4<10.## So ##c'_4=0,d'_2=4, x_{31}=3, x_{32}=0,q_3=(1,3),##

##t=4, q_4=q(4)=(0,0,0),## so ##c_5=0, d_4=0, x_{41}=0, x_{42}=0,q_4=(0,0),##

##t=5, q_5=q(5)=(0,0,0),## so ##c_6=0, d_5=0, x_{51}=0, x_{52}=0,q_5=(0,0).##

Thank you in advance
 

Attachments

  • Anthony W. Knapp-Advanced Algebra (2016) pp 264- 270-images-0.webp
    Anthony W. Knapp-Advanced Algebra (2016) pp 264- 270-images-0.webp
    34.3 KB · Views: 38
  • Anthony W. Knapp-Advanced Algebra (2016) pp 264- 270-images-1.webp
    Anthony W. Knapp-Advanced Algebra (2016) pp 264- 270-images-1.webp
    32.9 KB · Views: 16
  • Anthony W. Knapp-Advanced Algebra (2016) pp 264- 270-images-2.webp
    Anthony W. Knapp-Advanced Algebra (2016) pp 264- 270-images-2.webp
    33.7 KB · Views: 20
  • Anthony W. Knapp-Advanced Algebra (2016) pp 264- 270-images-3.webp
    Anthony W. Knapp-Advanced Algebra (2016) pp 264- 270-images-3.webp
    36.8 KB · Views: 45
  • Anthony W. Knapp-Advanced Algebra (2016) pp 264- 270-images-4.webp
    Anthony W. Knapp-Advanced Algebra (2016) pp 264- 270-images-4.webp
    34.3 KB · Views: 19
  • Anthony W. Knapp-Advanced Algebra (2016) pp 264- 270-images-5.webp
    Anthony W. Knapp-Advanced Algebra (2016) pp 264- 270-images-5.webp
    39.4 KB · Views: 35
  • Anthony W. Knapp-Advanced Algebra (2016) pp 264- 270-images-6.webp
    Anthony W. Knapp-Advanced Algebra (2016) pp 264- 270-images-6.webp
    30.9 KB · Views: 33
  • Velleman 1.webp
    Velleman 1.webp
    9.1 KB · Views: 23

Similar threads

  • · Replies 0 ·
Replies
0
Views
910
  • · Replies 4 ·
Replies
4
Views
3K
Replies
14
Views
2K
  • · Replies 1 ·
Replies
1
Views
1K
  • · Replies 11 ·
Replies
11
Views
1K
  • · Replies 67 ·
3
Replies
67
Views
11K
Replies
7
Views
8K
  • · Replies 52 ·
2
Replies
52
Views
13K
  • · Replies 6 ·
Replies
6
Views
2K
  • · Replies 5 ·
Replies
5
Views
2K