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'...


1

$L_1$, $L_2$ and $L_4$ are correct (notice that you are not showing that $L_2$ is not regular and $L_4$ is not context-free, which can be done using the appropriate version of the pumping lemma). As far as $L_3$ is concerned, let $x$ be the number that is encoded in binary and call $x_i$ its $i$-th least significant bit, indexed from $0$. Then, counting ...


1

In a nondeterministic automaton, a given string may have multiple possible paths through the automaton, since the path may include $\varepsilon$-transitions and may reach nodes where there is more than one possible non-$\varepsilon$-transition. A given string may also have no possible path if all the ways to traverse the automaton reach a point where there ...


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 ...


20

The concept has been researched before. (Once you know the answer, google for it ...) First there is old work by Book and Chandra, with the following abstract. Summary. It is shown that for every finite-state automaton there exists an equivalent nondeterministic automaton with a planar state graph. However there exist finite-state automata with no ...


29

It isn't true that every DFA for this language is non-planar: Here is a language that is truly non-planar: $$ \left\{ x \in \{\sigma_1,\ldots,\sigma_6\}^* \middle| \sum_{i=1}^6 i\#_{\sigma_i}(x) \equiv 0 \pmod 7 \right\}. $$ Take any planar FSA for this language. If we remove all unreachable states, we still get a planar graph. Each reachable state has six ...


1

The claim holds only for languages over finite alphabets. Bounded $L$ $\implies$ Finite $L$ Let $\Sigma$ be the alphabet of $L$ and $L$ be bounded by some $n \in \mathbb{N}$. The largest possible such $L$, call it $L^\#$, is $\bigcup_{\,i=0}^{\,n} \Sigma^i$ elements. $L^\#$ is finite since $|L^\#| = \sum_{i=0}^{n} |\Sigma|^i$. Therefore, any $L \subseteq ...


0

There is no nontrivial monoid in LI. LI is actually a (pseudo)-variety of finite semigroups: it is the class of finite semigroups $S$ such that, for every idempotent $e \in S$, $eSe = e$. If $S$ is a monoid, you can take $e = 1$, the identity of the monoid and get $S = 1S1 = 1$ so the monoid has to be trivial.


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

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

"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 ...


0

For each state $n \in N$, we maintain a set of states $E(n)$. Eventually, $E(n)$ would contain all states reachable from $n$ via $\epsilon$-transitions. You can think of $E$ as an array of sets. The notation $E(n)$ just means the value of $E$ at position $n$. So $E(p)$ is just the value of $E$ at position $p$.


1

You state two questions. (1) You are convinced that all the strings decribed by the RegEx are accepted by the DFA. In order to conclude equality you want to know the converse. Is every string accepted by the DFA also described by the RegEx? To do this, try to argue that every string accepted by the DFA consists of "blocks" of each time at least two the same ...


Top 50 recent answers are included