Tag Info

Hot answers tagged

4

Denote by $s(L)$ the number of states of the minimal (deterministic) automaton of a regular language $L$. The following result is proved in [1]. Let $A$ be a two letter alphabet and let $$ f(n) = \max \{s(L) \mid L \subseteq A^n\} $$ Thus $f(n)$ is the maximal number of states of the minimal automaton of a set of words of length $n$. Then $$ f(n) = ...


2

The number $n(1+b)$ is not prime because it has 2 divisors greater than 1. These are $(b+1)$ and $n$. I believe that's what is meant here.


1

How many states are required by a deterministic finite automaton to store m words each of length n? Like J.-E. Pin seems, I too believe this means no bit words, but plain old symbol words (which only makes a difference if the alphabet has three symbols or more). So the DFA has an alphabet $\Sigma$ and we have the task to make it accept $m$ given ...


1

Though finite-state automata do not have any form of "memory" (unlike, say, pushdown automata), it is possible to use the states themselves to store a finite amount of data, in the form of $n$ bits that the automaton can access at any time. In particular, define an n-bit automaton (not standard terminology) as something like a finite-state automaton except: ...


1

To elaborate Jims comment: Let the 2-stack automaton have stacks $1$ and $2$ and the 3-stack automaton we want to emulate have stacks $A,B$ and $C$. At the beginning of an operation, stack 1 shall consist of elements from stack A paired with the symbol $a$, written as $(a,e_a)$ and stack 2 shall consist of entries $(m,e)$ where $m \in \{b,c\}$ and $e$ is ...


1

You can make a transition that deposits two tokens at P2 if you want to (namely by having two parallel edges from T1 to P2, or if the formalism doesn't allow that, by depositing an extra token in a new dummy place from which it will immediately move to P2). But you don't have to. Allowing a transition to destroy some tokens when it fires (or, conversely, to ...


1

The point is that whenever you have a word in the language, you can assume without loss of generality that the length of the $w$ component is exactly one symbol. If somebody gives you a word with a longer $w$, you can just move all of the symbols except for the first into $x$ and $y$ instead, and get a different proof that the same word is in the language. ...



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