Opened 6 years ago

Closed 4 years ago

#15267 closed enhancement (fixed)

automaton: iterator over words of language

Reported by: dkrenn Owned by:
Priority: major Milestone: sage-6.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) Commit: 12180efb26373130d8eb8c03478fcd6e22e0d779
Dependencies: #18114, #18118 Stopgaps:

Description (last modified by dkrenn)

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

  • Description modified (diff)

comment:2 Changed 6 years ago by dkrenn

  • Keywords automatic sequences added

comment:3 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:4 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:5 Changed 5 years ago by cheuberg

  • Component changed from combinatorics to finite state machines

comment:6 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:7 Changed 4 years ago by dkrenn

  • Branch set to u/dkrenn/fsm/languages

comment:8 Changed 4 years ago by dkrenn

  • 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

Last 10 new commits:

39c9f14process iterator: add write_in_every_step flag
b25d39dimplement _FSMProcessIteratorAll_ and correct TapeCacheDetectAll
2f5796ewrite_in_every_step documented in process
84e90d3option process_iterator_class
dfdde86language-method for FSMs
84f5dd3language-method for automata
a277da9include language in toc
2f657ebdescribe kwargs (link to)
ea7e1c7more seealsos
0797263document and doctest iteration without restriction

comment:9 Changed 4 years ago by git

  • Commit changed from 0797263da029e6dd3444d99793420a74b1dc0f6d to 3d3039b63ac494f16e3b5ea4ef14dbfdb28acc38

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

54c99b9implement type-simple-iterator
9bf4d02iter_process_simple: docstring and small renaming of parameter
9376b18improved doctests (using words)
3d3039bMerge branch 'fsm/iter_process-simple' into fsm/words

comment:10 Changed 4 years ago by dkrenn

  • Authors set to Daniel Krenn
  • Dependencies changed from #15078, #18114 to #15078, #18114, #18118

Merge #18118 to avoid merge conflict.

comment:11 Changed 4 years ago by git

  • Commit changed from 3d3039b63ac494f16e3b5ea4ef14dbfdb28acc38 to 5d59d902e5f3d967fdba5a623ebab91554865183

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

ebe8c7badded tests to check that A.transducer(...).input_projection gives A
b604319improve docstring according to comments on trac
f209b0frename Automaton.transducer to Automaton.with_output
06842f6additional doctests/examples
cdcd3c0seealso-blocks
8bd4296Merge branch 't/18114/fsm/automaton-to-transducer' into t/15267/fsm/languages
5d59d90adapt code after merge to pass doctests

comment:12 Changed 4 years ago by cheuberg

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

comment:13 Changed 4 years ago by git

  • Commit changed from 5d59d902e5f3d967fdba5a623ebab91554865183 to e439bf224272bf353852425e642ba598fe9bad0a

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

e439bf2Trac #15267: Reviewer patch: Use ZZ(..., base=2)

comment:14 follow-up: Changed 4 years ago by cheuberg

  • Status changed from needs_review to needs_work
  • please cross-review 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 4 years ago by cheuberg

  • Milestone changed from sage-6.4 to sage-6.7

comment:16 Changed 4 years ago by cheuberg

  • Reviewers set to Clemens Heuberger

comment:17 Changed 4 years ago by dkrenn

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

comment:18 in reply to: ↑ 14 Changed 4 years ago by dkrenn

  • Commit changed from e439bf224272bf353852425e642ba598fe9bad0a to 7c9a1647aa60f71b7553c816d4b1993306dc47c2
  • Status changed from needs_work to needs_review

Replying to cheuberg:

  • please cross-review 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:

6e47b1dminor rephrase doc: remove one "only"
80d8798rename write_in_every_step and rephrase doc
7c9a164rephrase/extend doc of process_iterator_class

comment:19 Changed 4 years ago by cheuberg

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

comment:20 Changed 4 years ago by cheuberg

  • Commit changed from 7c9a1647aa60f71b7553c816d4b1993306dc47c2 to 12180efb26373130d8eb8c03478fcd6e22e0d779
  • Milestone changed from sage-6.7 to sage-6.9
  • Status changed from needs_review to positive_review

Modifications are fine, I add a minor commit.


New commits:

12180efTrac #15267: Reviewer commit: minor rewording docstring

comment:21 Changed 4 years ago by vbraun

  • Dependencies changed from #15078, #18114, #18118 to #18114, #18118

comment:22 Changed 4 years ago by vbraun

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