New answers tagged automata
0
Your initial automaton has two final states. Its reverse should have two initial states. You wanted to avoid that, and added a new initial state.
The proper construction just uses the two initial states. The determinization algorithm can handle that.
0
If you want a guarantee, then yes, verification is the only approach. That's pretty much the definition of what verification means.
If you want a heuristic check, there are a number of testing methods based on synthesizing test cases (perhaps based on the DFA) and then checking that the vending machine's actual behavior on those test cases matches your DFA'...
0
I assume that when you say "a divisible by 3 and b should also be divisible by 3" you mean that the number of $a$ characters in an accepted string must be a multiple of $3$, and the number of $b$ characters must also be a multiple of $3$. I am also going to assume that an empty string is accepted, since it contains $0$ $a$s and $0$ $b$s.
You will need ...
2
Hint. Consider a word a length $\geqslant k$ accepted by $M$ and a successful path for this word. Now prove that this path goes at least twice through the same state, thus producing a loop.
0
The lexicographic order is defined on words, not on regular expressions. An interesting exercise is to describe the restriction of the lexicographic order to the language $a^*b^*$, assuming that $a < b$. Note for instance that
$1 < a < a^2 < \dotsm < a^n < \dotsm$, but $\dotsm <a^nb <\dotsm <a^2b < ab < b$.
0
Your equation holds. Actually, more generally, for every subsets $S_1$, $S_2$ of $Q$ and for every words $u$, $v$ and $w$, the following equality holds
$$
(S_1u + S_2v)w = S_1uw + S_2vw
$$
Indeed,
\begin{align}
S_1u &= \{ p \in Q \mid \text{there is a path of the form $s_1 \xrightarrow{u} p$ for some state $s_1 \in S_1$} \} \\
S_2v &= \{ p \...
1
Your first language isn't regular. Here is a simple way of showing this. Consider all words in your language of the form $a^*c^*$; if your language were regular, then so would be that language. However, the new language is generated by the grammar $L \to \epsilon \mid aLcc$ (this requires an argument), and so is $\{a^n (cc)^n : n \geq 0\}$, which is ...
0
Your automaton will have $k$ states, one for each possible value of $m$, i.e., one for each of the congruence $(\text{mod } k)$ classes. Exactly one of these states will be marked as the final state, because that will be the one that accepts ocurrences of $\alpha$ that are compatible with $x ( \text{mod } k) =m$.
The transition function will connect states ...
0
"Containing 01111110" is easily handled directly with an DFA. Start with something that just recognizes that string; check for each state what you should do to loop back if mismatch (i.e., after 1 if a premature 0 shows up, you have to start over looking for a 1; if the second 0 isn't there, start over at the beginning). After you got your target, anything ...
5
You got the definition of $L^+$ wrong. It is not $L^* \setminus \{\epsilon\}$. Rather, it is
$$
L^+ = \bigcup_{n=1}^* L^n.
$$
You can check that $\epsilon \in L^+$ iff $\epsilon \in L$. Therefore:
If $\epsilon \notin L$ then $L^+ = L^*\setminus\{\epsilon\}$.
If $\epsilon \in L$ then $L^+ = L^*$.
0
Linear-bounded automata accept the class of context-sensitive languages. In contrast, Turing machine (deterministic as well as nondeterministic) accept the class of recursive languages. Every context-sensitive language is recursive, but the converse doesn't hold. For example, the halting problem for nondeterministic Turing machines running in space $n^2$ is ...
2
If you have $g$ symbols (including a blank) and a tape of size $n$ then there are $g^n$ words of length $n$. This is really basic combinatorics: The reasoning is that you have $g$ options for the first symbol, $g$ options for the second symbol, i.e. $g^2$ options for the first two symbols. Then again $g$ options for the third symbol, giving you $g^3$ options ...
Top 50 recent answers are included
