New answers tagged automata-theory
2
This seems to be exactly the type of question studied by Moses Ganardi and
coauthors in recent years. In particular this paper and this extension
prove nice trichotomies.
4
Let $L$ be the set of powers of 2 encoded in base 3. The encoding of $4^n$ in base 3 ends with 1, whereas the encoding of $2\cdot 4^n$ in base 3 ends with 2. Hence $L' = L \cap \Sigma^*1$ is the encoding of all powers of 4.
The encoding of an integer $m > 0$ in base 3 takes $\lceil \log_3 (m+1) \rceil$ digits. Since neither $4^n$ nor $4^n+1$ are powers ...
5
The precise answer depends on your model of PDA (models differ among different authors; compare Sipser to Hopcroft &Ullman). And number of states alone is not a good measure for PDA's, because there is a well-known tradeoff between states and stack symbols. For example, a classic construction turns a grammar like
S -> X_1 X_1
X_1 -> X_2 X_2
X_2 -> ...
4
(Answer inspired by Lamine's comment)
We assume the automaton is only allowed to push one symbol per state (otherwise, you could make the stack arbitrarily large with only two states). With a stack alphabet of size $k$, we can construct an automaton that accepts a word of length $O(n^{k+c})$.
The basic idea is to just make the stack as large as possible, ...
6
It seems it would depend on your particular model, in particular what information you have access to.
From what I infer, you are thinking of the following model:
you have a memory $m$, for instance of size $O(\log n)$.
at each step, you read a new letter $a\in\Sigma$ of your stream, and you are allowed to modify your memory $m$
you then have to say whether ...
Top 50 recent answers are included
