New answers tagged

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