# Tag Info

## Hot answers tagged automata

2

The most direct approach is the one suggested by amd in the comments: the language in question corresponds to the regular expression $b^*a^*$, since if you once get an $a$, you cannot ever again get a $b$. None the less, your first approach will work, but instead of working from $(a+b)^*ab(a+b)^*$, design the machine directly. If $q_0$ is the initial state, ...

2

In a semigroup $S$ (denoted multiplicatively) an absorbing element or annihilating element or zero element is an element $z$ of $S$ such that, for all $s \in S$, $zs = z = sz$. In particular, the set of all languages is a semigroup under concatenation. This semigroup has a unique zero, namely the empty set, since the equality $L \emptyset = \emptyset ... 2 A word in$X$of length$n\ge3$ends in a one followed by$0\le k\le2$zeros, and what comes before the one is a word in$X$of length$n-k-1$; so$s_n=s_{n-1}+s_{n-2}+s_{n-3}$. 1 First, it’s not true that every NFA is a DFA: exactly the opposite is true. (Judging by your question, this might even have been what you were actually thinking.) What you’ve already proved therefore shows that every DFA can be converted to an NFA with a single acceptor state, but it doesn’t prove that every DFA can be converted to a DFA with a single ... 1 See the following link for an explicit definition of closure properties, and some examples: http://infolab.stanford.edu/~ullman/ialc/spr10/slides/rs2.pdf Basically, if we say that a set of objects is closed under some operation, we mean that performing the operation on elements of the set produces elements that still lie in the set. In this case, the set ... 1 Loosely speaking, a DFA will have a state for each fact that it needs to “remember” about its input. This may require adding nodes to sort out what’s going on in NFA$\lambda$-transitions. Returning to a previous state isn’t a big deal: a transition can take you to a “previous” state. The old KMP string search algorithm, which is really a DFA in disguise ... 1 In question$1$, you can manipulate the equation a bit and get$n = m \pmod 3$. This isn't vital or very profound, but it may help your thinking. For both of these, you can take different paths depending on the number of$a$'s you get. The first part that deals with$a$'s will always be the same. You should have three states$X$,$Y$,$YZ\$ with the ...

Only top voted, non community-wiki answers of a minimum length are eligible