Opened 8 years ago
Closed 6 years ago
#15267 closed enhancement (fixed)
automaton: iterator over words of language
Reported by:  dkrenn  Owned by:  

Priority:  major  Milestone:  sage6.9 
Component:  finite state machines  Keywords:  automata, finite state machines, language, iterator, automatic sequences, sd66 
Cc:  cheuberg, skropf  Merged in:  
Authors:  Daniel Krenn  Reviewers:  Clemens Heuberger 
Report Upstream:  N/A  Work issues:  
Branch:  12180ef (Commits, GitHub, GitLab)  Commit:  12180efb26373130d8eb8c03478fcd6e22e0d779 
Dependencies:  #18114, #18118  Stopgaps: 
Description (last modified by )
Add a method language(self, n, initial_state)
to FiniteStateMachine
which returns an iterator over all words of length n recognized by the automaton/finite state machine. Possibly, use sage.combinat.words
.
See also ticket:15078#comment:10.
Change History (22)
comment:1 Changed 8 years ago by
 Description modified (diff)
comment:2 Changed 8 years ago by
 Keywords automatic sequences added
comment:3 Changed 8 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:4 Changed 7 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:5 Changed 7 years ago by
 Component changed from combinatorics to finite state machines
comment:6 Changed 7 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:7 Changed 6 years ago by
 Branch set to u/dkrenn/fsm/languages
comment:8 Changed 6 years ago by
 Cc cheuberg skropf added
 Commit set to 0797263da029e6dd3444d99793420a74b1dc0f6d
 Dependencies changed from #15078 to #15078, #18114
 Keywords sd66 added
 Status changed from new to needs_review
comment:9 Changed 6 years ago by
 Commit changed from 0797263da029e6dd3444d99793420a74b1dc0f6d to 3d3039b63ac494f16e3b5ea4ef14dbfdb28acc38
comment:10 Changed 6 years ago by
 Dependencies changed from #15078, #18114 to #15078, #18114, #18118
Merge #18118 to avoid merge conflict.
comment:11 Changed 6 years ago by
 Commit changed from 3d3039b63ac494f16e3b5ea4ef14dbfdb28acc38 to 5d59d902e5f3d967fdba5a623ebab91554865183
Branch pushed to git repo; I updated commit sha1. New commits:
ebe8c7b  added tests to check that A.transducer(...).input_projection gives A

b604319  improve docstring according to comments on trac

f209b0f  rename Automaton.transducer to Automaton.with_output

06842f6  additional doctests/examples

cdcd3c0  seealsoblocks

8bd4296  Merge branch 't/18114/fsm/automatontotransducer' into t/15267/fsm/languages

5d59d90  adapt code after merge to pass doctests

comment:12 Changed 6 years ago by
 Branch changed from u/dkrenn/fsm/languages to u/cheuberg/fsm/languages
comment:13 Changed 6 years ago by
 Commit changed from 5d59d902e5f3d967fdba5a623ebab91554865183 to e439bf224272bf353852425e642ba598fe9bad0a
Branch pushed to git repo; I updated commit sha1. New commits:
e439bf2  Trac #15267: Reviewer patch: Use ZZ(..., base=2)

comment:14 followup: ↓ 18 Changed 6 years ago by
 Status changed from needs_review to needs_work
 please crossreview reviewer patch.
 documentation of the parameter
write_in_every_step
is unclear in all occurrences: what does "the output is stored" mean? It seems that it means that instead of processing the input word, all prefixes of the input word are processed.  parameter
process_iterator_class
: the consequences of setting this parameter are not explained. _FSMProcessIteratorAll_
: "but only accepts": remove "only"?
comment:15 Changed 6 years ago by
 Milestone changed from sage6.4 to sage6.7
comment:16 Changed 6 years ago by
 Reviewers set to Clemens Heuberger
comment:17 Changed 6 years ago by
 Branch changed from u/cheuberg/fsm/languages to u/dkrenn/fsm/languages
comment:18 in reply to: ↑ 14 Changed 6 years ago by
 Commit changed from e439bf224272bf353852425e642ba598fe9bad0a to 7c9a1647aa60f71b7553c816d4b1993306dc47c2
 Status changed from needs_work to needs_review
Replying to cheuberg:
 please crossreview reviewer patch.
Done; looks ok.
 documentation of the parameter
write_in_every_step
is unclear in all occurrences: what does "the output is stored" mean? It seems that it means that instead of processing the input word, all prefixes of the input word are processed.
Renamed and rewritten.
 parameter
process_iterator_class
: the consequences of setting this parameter are not explained.
Explained.
_FSMProcessIteratorAll_
: "but only accepts": remove "only"?
Done.
New commits:
6e47b1d  minor rephrase doc: remove one "only"

80d8798  rename write_in_every_step and rephrase doc

7c9a164  rephrase/extend doc of process_iterator_class

comment:19 Changed 6 years ago by
 Branch changed from u/dkrenn/fsm/languages to u/cheuberg/fsm/languages
comment:20 Changed 6 years ago by
 Commit changed from 7c9a1647aa60f71b7553c816d4b1993306dc47c2 to 12180efb26373130d8eb8c03478fcd6e22e0d779
 Milestone changed from sage6.7 to sage6.9
 Status changed from needs_review to positive_review
Modifications are fine, I add a minor commit.
New commits:
12180ef  Trac #15267: Reviewer commit: minor rewording docstring

comment:21 Changed 6 years ago by
 Dependencies changed from #15078, #18114, #18118 to #18114, #18118
comment:22 Changed 6 years ago by
 Branch changed from u/cheuberg/fsm/languages to 12180efb26373130d8eb8c03478fcd6e22e0d779
 Resolution set to fixed
 Status changed from positive_review to closed
Note: See
TracTickets for help on using
tickets.
Last 10 new commits:
process iterator: add write_in_every_step flag
implement _FSMProcessIteratorAll_ and correct TapeCacheDetectAll
write_in_every_step documented in process
option process_iterator_class
languagemethod for FSMs
languagemethod for automata
include language in toc
describe kwargs (link to)
more seealsos
document and doctest iteration without restriction