# Tag Info

## New answers tagged automata

### Help with understanding a stipulation in pumping lemma

Go back to how the pumping lemma is created: If L is regular then there is a state machine recognising L with p states. If you process the first n characters of a string, you must visit at least one ...
• 25.9k

• 1,254
Accepted

Actually your list of properties already solves the problem. As $\varepsilon$ is an element of $\Sigma^*$ and we cannot have any longer word due to the lack of symbols, we have $\varnothing^*=\{\... • 28.2k 4 votes Accepted ### pumping lemma length restrictions clarification First, for the sake of preciseness, note that the Lemma says that for every regular language$L$, there exists a constant$m\ge 1$, such that for every word$w\in L$... [what you wrote]. That is, the ... • 16.5k 2 votes ### Free description of the Kameda-Weiner algorithm? Here is a succinct but somewhat abstract description of the technique based on . Also reading  to understand the universal automaton before approaching this description is recommended. I am also ... 1 vote ### How to recognize all halting states of a turing machine? A turing machine is defined as a 7-tuple$M = \langle Q, \Gamma, b, \Sigma, \delta, q_0, F \rangle$. The set$F$in the tuple is the set of final states or accepting states. So any other states other ... • 170 2 votes Accepted ### Describing the Language of a DFA with 7 States To accept a string, you must start in$q_0$and end in$q_0$or in$q_3$. A path from$q_0$to$q_0$can make a cycle through$q_5$(so you can have$(ba)^*$) or through$q_1,q_2,q_3,q_4$(and so$a(...
• 835
Usually, the first symbol means what you expect to read from the input (1), the second what is the symbol at the top of the stack (2) and the third what will happen with the stack (3). $\lambda$ or \$\...