New answers tagged automata
0
Working with a queue automaton for me is intuitively equivalent to working with a circular tape.
Read the input $w$ from the automaton, and put it on the tape. Add two markers $A$ and $B$, so we obtain $Aw_1Bw_2$. Now we can one by one eat a letter after $A$ and one after $B$.
For the deterministic variant it suffices to put $B$ exactly in the middle of the ...
0
Use the pumping lemma: If $L$ is regular, there is a constant $N \ge 1$ such that any string $\sigma \in L$ can be divided as $\sigma =\alpha \beta \gamma$ with $\lvert \alpha \beta \rvert \le N$, $\beta \ne \varepsilon$ so that for all $k$ the string $\alpha \beta^k \gamma \in L$.
Proof is by contradiction. Assume your $L$ is regular, let $N$ be the lemma's ...
3
McCloskey gave such an algorithm in his paper An $O(n^2)$ Time Algorithm for Deciding
Whether a Regular Language is a Code. Given an NFA on $n$ states, his algorithm runs in time $O(n^2)$. Since a regular expression of length $n$ can be converted to an NFA with $O(n)$ states in linear time, McCloskey's algorithms runs in quadratic time even when given a ...
1
This can also be proved easily using Myhill-Nerode theorem.
Myhill-Nerode Theorem: Given a language $ L \subseteq \Sigma^* $, Suppose $$ \forall x,y \in S, (x \neq y) \wedge (\exists z \in \Sigma^*
,L(xz) \neq L(yz)) $$ where S is an infinite set. Then L is not a
regular language.
(Here $L(w) = 1$ if $w \in L$ and $L(w) = 0$ if $w \notin L$.)
For the ...
1
The LBA maintains a counter $c$, initialized by $1$, which is stored on a parallel track. It thinks of the rest of the tape as an integer $m$. It then repeatedly executes the following instructions: divide $m$ by $c$, and increment $c$. The algorithm terminates when one of the following happens: $m = 1$, in which case you can declare success; or $m$ is not ...
1
This is correct, and moreover it is tight for $n = 1$, even for a binary alphabet (but not for a unary alphabet!). Indeed, it is well-known that there are language accepted by $m$-state NFAs which require $2^m$ states for a DFA. Since the DFA complexity of a language and its complement coincide, taking $A_1 = \Sigma^*$ we obtain a tight example with $n = 1$ ...
0
A string is accepted by an NFA if there is a sequence of moves such that it can reach a final state at the end of the string.
As you said, assume that for $w=0110$ after reading $011$ we are in a final state (called $q$) and there is no transition like $\delta(q,0)$, this is when we encounter a situation called dead configuration. At this point we can't just ...
0
You almost got it Right in the comments, so I will give you the last push along with one way to think about it.
In the right automaton: the language of the automaton is simply $0\cdot L(q_1)$, where $L(q_1)$ is the set of words that can be accepted from $q_1$. Its not hard to see that a word $w$ is accepted from $q_1$ iff it $w$ is the empty word $\epsilon$,...
1
The Rule 110 cellular automaton is apparently Turing-complete. If you're not counting the cost of memory, I imagine a circuit that applies the Rule 110 evolution rules could be implemented with very few switches.
See also https://softwareengineering.stackexchange.com/q/230538/34181.
2
Here are the first few words accepted by the DFA on the right:
$$
0 \\
00 \\
000,010 \\
0000,0010,0100,0110 \\
00000,00010,00100,00110,01000,01010,01100,01110
$$
The DFA on the left accepts a subset of these words. Here are the words it does not accept:
$$
010 \\
0010,0100 \\
00010,00100,01000,01110
$$
Perhaps you can use these lists to obtain a guess on the ...
0
The following doesn't necessarily answer the question, but might be of interest.
Suppose that $L$ is a regular language consisting entirely of palindromes, and suppose that $L$ is accepted by a DFA having $n$ states. According to the pumping lemma, every word $w \in L$ of length at least $n$ can be decomposed as $xyz$ such that $|xy| \leq n$, $y \neq \...
2
I will give a general algorithm going through intermediate steps that can be implemented in polynomial time, each. Yet, I will not dive into the details of how to implement each step. The solution I'm suggesting may not be optimal, yet it is easy to understand. Essentially, we're going to rely on basic properties of Pushdown automata (PDAs, for short).
Let $\...
3
Consider a nondeterministic Büchi automaton $\mathcal{A} = \langle \Sigma, Q, q_0, \delta, \alpha\rangle$. The acceptance condition of $\mathcal{A}$ is a subset of states $\alpha\subseteq Q$, and an infinite run $r = q_0, q_1, q_2, \ldots$ over an infinite word $\sigma_1\sigma_2\cdots $ is accepting iff $r$ visits a state in $\alpha$ infinitely many times.
...
Top 50 recent answers are included
