Minimal automaton for a factorial, transitive, and rational language (Q1822985): Difference between revisions

A language is factorial if it contains all factors (i.e., subwords) of its words, and it is transitive if for any pair u, v of its words there exists a word w such that uwv is also in the language. A factorial, transitive, rational language is called an FTR-language. These languages can also be characterized as the languages recognizable by certain special finite automata for which the abbreviation ida is used. The author shows that every FTR-language has a minimal ida. Moreover, three ways of obtaining this minimal ida are presented.