Opened 6 years ago
Closed 6 years ago
#16143 closed enhancement (fixed)
finite_state_machine: Add an example on the Gray code into the documentation
Reported by:  cheuberg  Owned by:  

Priority:  minor  Milestone:  sage6.3 
Component:  combinatorics  Keywords:  finite_state_machine 
Cc:  skropf  Merged in:  
Authors:  Clemens Heuberger, Daniel Krenn, Sara Kropf  Reviewers:  Daniel Krenn, Sara Kropf 
Report Upstream:  N/A  Work issues:  
Branch:  301b5cb (Commits)  Commit:  301b5cb474e4dd06ba988ce319201cb1cc9daa4d 
Dependencies:  #16132, #16141, #16142  Stopgaps: 
Description
As an example on how to use cartesian products of transducers as introduced in #16061, a transducer converting standard binary expansion into Gray code is constructed by emulating the standard algorithm by xoring the the standard binary expansion with its shifted version.
The class collecting common transducers introduced in #16141 now also has a (hardcoded) version of the same transducer and it is made sure that both transducers agree.
Change History (19)
comment:1 Changed 6 years ago by
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
 Dependencies set to #16141
comment:3 Changed 6 years ago by
 Dependencies changed from #16141 to #16141, #16142
comment:4 Changed 6 years ago by
 Branch changed from u/cheuberg/fsm/example_gray_code to u/dkrenn/fsm/example_gray_code
 Cc dkrenn removed
 Commit changed from 6145b1f679ef60d78f888df417ed1591880c3d10 to 1efa597519da1fa32436e0e1e2dddf609cca391b
 Reviewers set to Daniel Krenn
comment:5 Changed 6 years ago by
 Branch changed from u/dkrenn/fsm/example_gray_code to u/cheuberg/fsm/example_gray_code
comment:6 Changed 6 years ago by
 Commit changed from 1efa597519da1fa32436e0e1e2dddf609cca391b to 5394265e3c6a7bd45db933a294916861f3e5e115
Modified example in finite_state_machine.py
to also have correct final states and compare it with the final states given by transducers.GrayCode
.
Corrected link from transducers.GrayCode
to this example.
comment:7 Changed 6 years ago by
 Branch changed from u/cheuberg/fsm/example_gray_code to u/dkrenn/fsm/example_gray_code
 Commit changed from 5394265e3c6a7bd45db933a294916861f3e5e115 to 82ceebabe1fd855777c70225336c644ce01ea522
Last 10 new commits:
4a53b09  Merge branch '#16132' into fsm/count_subblock_occurrences

5d65767  Edit doctests due to #16132 change.

e1bd1df  Merge branch 'fsm/count_subblock_occurrences' into fsm/operator_transducers

3110f9d  Edit doctests due to #16132 change.

6145b1f  Merge branch 'fsm/operator_transducers' into fsm/example_gray_code

1efa597  added final_states to Graycode transducer, improved docstring

1d3cb1e  changes in Graycode example

16c62dd  Constructed Gray code now also has correct final states.

5394265  Corrected link from transducers.GrayCode to example in finite_state_machine module

82ceeba  Merge remotetracking branch 'origin/u/cheuberg/fsm/example_gray_code' into u/cheuberg/fsm/example_gray_code

comment:8 Changed 6 years ago by
 Branch changed from u/dkrenn/fsm/example_gray_code to u/dkrenn/fsm/example_gray_codeonbeta8
 Commit changed from 82ceebabe1fd855777c70225336c644ce01ea522 to 2a6bafea46ca50feee5ab8129cbf58e8a67776b7
Now bases on beta8 + #16142.
Last 10 new commits:
6fed278  Merge branch 'fsm/operator_transducers' into fsm/example_gray_code

f7b3a35  Gray code example modified and prepackaged transducer

6145b1f  Merge branch 'fsm/operator_transducers' into fsm/example_gray_code

1efa597  added final_states to Graycode transducer, improved docstring

1d3cb1e  changes in Graycode example

16c62dd  Constructed Gray code now also has correct final states.

5394265  Corrected link from transducers.GrayCode to example in finite_state_machine module

82ceeba  Merge remotetracking branch 'origin/u/cheuberg/fsm/example_gray_code' into u/cheuberg/fsm/example_gray_code

826b764  Merge remotetracking branch 'origin/u/dkrenn/fsm/example_gray_code' into fsm/operator_transducersonbeta8

2a6bafe  corrected one doctest and added another (leftshift transducer)

comment:9 Changed 6 years ago by
 Branch changed from u/dkrenn/fsm/example_gray_codeonbeta8 to u/cheuberg/fsm/example_gray_code
 Commit changed from 2a6bafea46ca50feee5ab8129cbf58e8a67776b7 to 8c1cbb6192d491d4bf80e9393fc4dab60ae06e4e
Crossreviewed all changes by dkrenn, they are fine for me.
Corrected leftshift transducer (it is a rightshift transducer, as highlighted by the above doctest) and explained this.
comment:10 Changed 6 years ago by
 Dependencies changed from #16141, #16142 to #16132, #16141, #16142
comment:11 Changed 6 years ago by
 Branch changed from u/cheuberg/fsm/example_gray_code to u/dkrenn/fsm/example_gray_code
comment:12 followup: ↓ 13 Changed 6 years ago by
 Commit changed from 8c1cbb6192d491d4bf80e9393fc4dab60ae06e4e to 24b6d69df4a5c0c01445a20df1a3f865a9ffc5c0
Reviewed your changes...ok.
Rewrote/Extended? the documentation of the 'shift'part of the example. Please review.
New commits:
24b6d69  explained the shifting in the Gray codeconstruction differently

comment:13 in reply to: ↑ 12 Changed 6 years ago by
Replying to dkrenn:
Rewrote/Extended? the documentation of the 'shift'part of the example. Please review.
fine for me.
comment:14 Changed 6 years ago by
 Branch changed from u/dkrenn/fsm/example_gray_code to u/skropf/fsm/example_gray_code
 Commit changed from 24b6d69df4a5c0c01445a20df1a3f865a9ffc5c0 to 301b5cb474e4dd06ba988ce319201cb1cc9daa4d
I rewrote the documentation to clarify the position of the least significant digit and the direction of the shift. Please review.
Everthing else is fine for me.
comment:15 Changed 6 years ago by
fine for me.
comment:16 Changed 6 years ago by
 Reviewers changed from Daniel Krenn to Daniel Krenn, Sara Kropf
comment:17 Changed 6 years ago by
 Status changed from needs_review to positive_review
Fome also for me. Since all participants in this ticket agree, I give it a positive review.
comment:18 Changed 6 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:19 Changed 6 years ago by
 Branch changed from u/skropf/fsm/example_gray_code to 301b5cb474e4dd06ba988ce319201cb1cc9daa4d
 Resolution set to fixed
 Status changed from positive_review to closed
During the review I realized that the Graycode transducer (in generators) didn't have any final states. I've corrected this. I added a doctest to print the Gray code of the first 10 nonnegative integers. Please review my changes.
Last 10 new commits:
Fixed doctest for operator
Merge branch 'fsm/operator_transducers' into fsm/example_gray_code
Gray code example modified and prepackaged transducer
minor corrections
Merge branch '#16132' into fsm/count_subblock_occurrences
Edit doctests due to #16132 change.
Merge branch 'fsm/count_subblock_occurrences' into fsm/operator_transducers
Edit doctests due to #16132 change.
Merge branch 'fsm/operator_transducers' into fsm/example_gray_code
added final_states to Graycode transducer, improved docstring