Opened 5 years ago

Closed 5 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: sage-6.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 (hard-coded) version of the same transducer and it is made sure that both transducers agree.

Change History (19)

comment:1 Changed 5 years ago by cheuberg

  • Status changed from new to needs_review

comment:2 Changed 5 years ago by dkrenn

  • Dependencies set to #16141

comment:3 Changed 5 years ago by dkrenn

  • Dependencies changed from #16141 to #16141, #16142

comment:4 Changed 5 years ago by dkrenn

  • Authors changed from Clemens Heuberger to Clemens Heuberger, Daniel Krenn
  • 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

During the review I realized that the Gray-code 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 non-negative integers. Please review my changes.


Last 10 new commits:

9029a07Fixed doctest for operator
6fed278Merge branch 'fsm/operator_transducers' into fsm/example_gray_code
f7b3a35Gray code example modified and prepackaged transducer
7a907acminor corrections
4a53b09Merge branch '#16132' into fsm/count_subblock_occurrences
5d65767Edit doctests due to #16132 change.
e1bd1dfMerge branch 'fsm/count_subblock_occurrences' into fsm/operator_transducers
3110f9dEdit doctests due to #16132 change.
6145b1fMerge branch 'fsm/operator_transducers' into fsm/example_gray_code
1efa597added final_states to Gray-code transducer, improved docstring
Last edited 5 years ago by dkrenn (previous) (diff)

comment:5 Changed 5 years ago by cheuberg

  • Branch changed from u/dkrenn/fsm/example_gray_code to u/cheuberg/fsm/example_gray_code

comment:6 Changed 5 years ago by cheuberg

  • 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 5 years ago by dkrenn

  • 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:

4a53b09Merge branch '#16132' into fsm/count_subblock_occurrences
5d65767Edit doctests due to #16132 change.
e1bd1dfMerge branch 'fsm/count_subblock_occurrences' into fsm/operator_transducers
3110f9dEdit doctests due to #16132 change.
6145b1fMerge branch 'fsm/operator_transducers' into fsm/example_gray_code
1efa597added final_states to Gray-code transducer, improved docstring
1d3cb1echanges in Gray-code example
16c62ddConstructed Gray code now also has correct final states.
5394265Corrected link from transducers.GrayCode to example in finite_state_machine module
82ceebaMerge remote-tracking branch 'origin/u/cheuberg/fsm/example_gray_code' into u/cheuberg/fsm/example_gray_code

comment:8 Changed 5 years ago by dkrenn

  • Branch changed from u/dkrenn/fsm/example_gray_code to u/dkrenn/fsm/example_gray_code-on-beta8
  • Commit changed from 82ceebabe1fd855777c70225336c644ce01ea522 to 2a6bafea46ca50feee5ab8129cbf58e8a67776b7

Now bases on beta8 + #16142.


Last 10 new commits:

6fed278Merge branch 'fsm/operator_transducers' into fsm/example_gray_code
f7b3a35Gray code example modified and prepackaged transducer
6145b1fMerge branch 'fsm/operator_transducers' into fsm/example_gray_code
1efa597added final_states to Gray-code transducer, improved docstring
1d3cb1echanges in Gray-code example
16c62ddConstructed Gray code now also has correct final states.
5394265Corrected link from transducers.GrayCode to example in finite_state_machine module
82ceebaMerge remote-tracking branch 'origin/u/cheuberg/fsm/example_gray_code' into u/cheuberg/fsm/example_gray_code
826b764Merge remote-tracking branch 'origin/u/dkrenn/fsm/example_gray_code' into fsm/operator_transducers-on-beta8
2a6bafecorrected one doctest and added another (left-shift transducer)

comment:9 Changed 5 years ago by cheuberg

  • Branch changed from u/dkrenn/fsm/example_gray_code-on-beta8 to u/cheuberg/fsm/example_gray_code
  • Commit changed from 2a6bafea46ca50feee5ab8129cbf58e8a67776b7 to 8c1cbb6192d491d4bf80e9393fc4dab60ae06e4e

Cross-reviewed all changes by dkrenn, they are fine for me.

Corrected left-shift transducer (it is a right-shift transducer, as highlighted by the above doctest) and explained this.

comment:10 Changed 5 years ago by cheuberg

  • Dependencies changed from #16141, #16142 to #16132, #16141, #16142

comment:11 Changed 5 years ago by dkrenn

  • Branch changed from u/cheuberg/fsm/example_gray_code to u/dkrenn/fsm/example_gray_code

comment:12 follow-up: Changed 5 years ago by dkrenn

  • 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:

24b6d69explained the shifting in the Gray code-construction differently

comment:13 in reply to: ↑ 12 Changed 5 years ago by cheuberg

Replying to dkrenn:

Rewrote/Extended? the documentation of the 'shift'-part of the example. Please review.

fine for me.

comment:14 Changed 5 years ago by skropf

  • 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 5 years ago by cheuberg

fine for me.

comment:16 Changed 5 years ago by skropf

  • Authors changed from Clemens Heuberger, Daniel Krenn to Clemens Heuberger, Daniel Krenn, Sara Kropf
  • Reviewers changed from Daniel Krenn to Daniel Krenn, Sara Kropf

comment:17 Changed 5 years ago by dkrenn

  • 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 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:19 Changed 5 years ago by vbraun

  • Branch changed from u/skropf/fsm/example_gray_code to 301b5cb474e4dd06ba988ce319201cb1cc9daa4d
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.