Hot answers tagged

4

You can always make a non-deterministic automaton with a single accepting state for any regular language (even without $\varepsilon$-transitions) -- unless the language contains the empty string and is not closed under concatenation. Just take an automaton without this restriction and create a new accepting state, and then for each transtion into a state ...


3

According to Eilenberg [1, Chap. IV, Prop. 1.1], the following result holds: Proposition. For any nonempty subset $L$ of $A^*$, the following conditions are equivalent: for all $u, v \in L$, $u^{-1}L = v^{-1}L$, the minimal automaton of $L$ has a single final state, $L$ is recognized by a deterministic automaton with a single final state that ...


2

Have a look at $$\begin{align}S&\to \epsilon \mid aSB\\ B&\to b\mid bb\end{align} $$


1

You are mistakenly assuming the word is purely morphic. A morphic word is the image of a purely morphic word by some morphism, i.e. there could be secretly different kinds of $0$ and different kinds of $1$ in the purely morphic version of the word, whose difference then get erased by the end morphism. Since the word is supposedly $2$-automatic, to ...


1

Firstly, your intuition about how such a program would work is absolutely correct, and for all effective purposes would be completely satisfactory (in my view). Secondly, as you probably know, prime numbers must be defined in terms of multiplication/division because prime numbers have exactly 2 factors (factorization being a concept developed from ...



Only top voted, non community-wiki answers of a minimum length are eligible