Opened 8 years ago

Closed 8 years ago

#16255 closed enhancement (fixed)

FiniteStateMachine.with_final_word_out: New method

Reported by: cheuberg Owned by:
Priority: major Milestone: sage-6.3
Component: combinatorics Keywords: finite_state_machine
Cc: skropf Merged in:
Authors: Clemens Heuberger, Daniel Krenn Reviewers: Daniel Krenn, Sara Kropf
Report Upstream: N/A Work issues:
Branch: 7db5774 (Commits, GitHub, GitLab) Commit: 7db57742c744f66ae944ea22231a55c9ca498514
Dependencies: #16145, #16206, #16207, #16253 Stopgaps:

Status badges

Description (last modified by cheuberg)

Constructs a finite state machine with final output words for all states by implicitly reading trailing letters until a final state is reached. This is e.g. useful for finite state machines operating on digit expansions: there, it is sometimes required to read a sufficient number of trailing zeros (at the most significant positions) in order to reach a final state and to flush all carries. In this case, this method constructs an essentially equivalent finite state machine in the sense that it not longer requires adding sufficiently many trailing zeros. However, it is the responsibility of the user to make sure that if adding trailing zeros to the input anyway, the output is equivalent.

Change History (14)

comment:1 Changed 8 years ago by cheuberg

  • Branch set to u/cheuberg/fsm/with_final_word_out
  • Commit set to 2c11f6a0024ee6c7a663ea687c9d44c6b987b348
  • Description modified (diff)
  • Status changed from new to needs_review

Last 10 new commits:

d5d08ccDeleted a check for consistency in _latex_
0469d11reworded ValueError (joined sentences)
df6f9fbreviewer patch: line breaks in documentation
bbe0866reworded two docstrings
21392c5added doctests to FSMState.deepcopy to check that deepcopy of a property works
696f66eFiniteStateMachine.with_final_word_out: New method
c15e3d8Small changes in the documentation of with_final_word_out
0312268line break in docstring
e0963c4FiniteStateMachine.with_final_word_out: replace "loop" by "cycle"
2c11f6aFiniteStateMachine.with_final_word_out: only support transitions with input labels of length 1

comment:2 Changed 8 years ago by dkrenn

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

comment:3 Changed 8 years ago by dkrenn

  • Authors changed from Clemens Heuberger to Clemens Heuberger, Daniel Krenn
  • Cc dkrenn removed
  • Commit changed from 2c11f6a0024ee6c7a663ea687c9d44c6b987b348 to fe32df836177f9eadf140014160701b503b7c6aa
  • Reviewers set to Daniel Krenn

I've did a very careful reviewing. Everything was fine. I decided to extend its functionality. Please review those changes.


New commits:

fe32df8extending functionality of with_final_word_out and inplace-version

comment:4 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:5 Changed 8 years ago by skropf

  • Branch changed from u/dkrenn/fsm/with_final_word_out to u/skropf/fsm/with_final_word_out

comment:6 Changed 8 years ago by cheuberg

  • Branch changed from u/skropf/fsm/with_final_word_out to u/cheuberg/fsm/with_final_word_out

comment:7 Changed 8 years ago by cheuberg

  • Commit changed from fe32df836177f9eadf140014160701b503b7c6aa to 1382dec088477ed314f206715e83a844690b2c2c

Last 10 new commits:

21392c5added doctests to FSMState.deepcopy to check that deepcopy of a property works
696f66eFiniteStateMachine.with_final_word_out: New method
c15e3d8Small changes in the documentation of with_final_word_out
0312268line break in docstring
e0963c4FiniteStateMachine.with_final_word_out: replace "loop" by "cycle"
2c11f6aFiniteStateMachine.with_final_word_out: only support transitions with input labels of length 1
fe32df8extending functionality of with_final_word_out and inplace-version
134fd7eAdded explanations in documentation of Transducer.with_final_word_out
b9bfd58renamed parameter allow_not_accepting to allow_non_final; docstring improvements
1382decRewrote with_final_output to cache all intermediate results.

comment:8 Changed 8 years ago by cheuberg

I rewrote some docstrings, then I rewrote

fe32df8extending functionality of with_final_word_out and inplace-version

so that all intermediate results are cached. Please review.

comment:9 Changed 8 years ago by git

  • Commit changed from 1382dec088477ed314f206715e83a844690b2c2c to a466e625f539a576b9790e7022bb6373f05fb1cc

Branch pushed to git repo; I updated commit sha1. New commits:

a466e62FiniteStateMachine.__init__: allow with_final_word_out=0

comment:10 Changed 8 years ago by git

  • Commit changed from a466e625f539a576b9790e7022bb6373f05fb1cc to 5135618522e478115b5e0d342f08cf0bbbbe4fa0

Branch pushed to git repo; I updated commit sha1. New commits:

5135618trac #16255: add doctest for last commit

comment:11 Changed 8 years ago by skropf

  • Branch changed from u/cheuberg/fsm/with_final_word_out to u/skropf/fsm/with_final_word_out
  • Commit changed from 5135618522e478115b5e0d342f08cf0bbbbe4fa0 to 5ca61d1e7360dfb54b4b65605e7be4f125734dae
  • Reviewers changed from Daniel Krenn to Daniel Krenn, Sara Kropf

I added a doctest and a comment to clarify that final states with empty final output are considered in the right way.


New commits:

5ca61d1FiniteStateMachine.construct_final_word_out: clarified difference between None and empty list

comment:12 Changed 8 years ago by dkrenn

  • Branch changed from u/skropf/fsm/with_final_word_out to u/dkrenn/fsm/with_final_word_out

comment:13 Changed 8 years ago by dkrenn

  • Commit changed from 5ca61d1e7360dfb54b4b65605e7be4f125734dae to 7db57742c744f66ae944ea22231a55c9ca498514
  • Status changed from needs_review to positive_review

Reviewed the changes. Everything looks fine now.


New commits:

7db5774added spaces after comment-symbol in code

comment:14 Changed 8 years ago by vbraun

  • Branch changed from u/dkrenn/fsm/with_final_word_out to 7db57742c744f66ae944ea22231a55c9ca498514
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.