Search Results

To expand a little on Ran G.'s comment, given a pumping length of $p$, we can take the string $s=a^{p}b^{p} \in A$, then splitting into $s=xyz$, the $y$ section (the part that can be pumped) must be a …

Assuming by "$.$" you mean concatention ($\circ$ when made explicit by Sipser) and by $\phi$ you mean $\emptyset$, I'm not sure what the confusion is. Sipser is claiming that sometimes (in almost ever …

No, NFAs can have any number of transitions for a given symbol1 from a state. If the NFA gets into the situation where the current symbol from the input has no transition from the current state, then …

It depends on whether the NFA contains a path for every possible word. If there is an input word where there is no path through the NFA at all labelled with that word, then yes, this can happen. See …

As Renato suggests, you never need to change state in a PDA. Even without useing a CFG as an intermediate, we can take a PDA and construct another that does the same job with using only a single state …

You can break the problem down into two parts: strings that make it to state $r$, and strings that, starting at $r$, make it to an accepting state. To get a DFA $M'$ for the first one, we take $M$, m …

Yes, we can simply make the starting state an accept state. With no input (i.e. empty string) the machine halts immediately, and accepts.

Your methodology for creating the DFA from the NFA is fine. The problem is that you started with the wrong NFA (you'll notice that your NFA doesn't accept abbaa either). Try this one instead:

Your diagram looks like you have the correct answer. Just for comparison: Somewhat overannotated, but I don't think I've missed anything. As best I can tell, your diagram expresses the same idea.

Your DFA is close, but not quite right. Note that the description requires the strings in the language to have at least one $a$, whereas your DFA will accept the empty string. The fix is simple of cou …

This behaviour can occur even with very small automata (i.e. where the number of states $m$ is a fixed constant). …

The problem here is not really in the implementation of the DFA, but in understanding what the DFA is doing. With those who have access to the text, careful reading of the algorithm preceding it shoul …

It is true that this construction may result in a DFA with unreachable states. The general construction begins simply by including all possible states, then adding the appropriate transitions, so typi …

As scaaahu notes in the comments, by a common definition, a deterministic finite automaton (DFA) must have a transition from every state on every alphabet symbol, i.e. the transition function $\delta( …

Your guess is definitely on the right track, though you may need one more piece of information. As you have infinite states (of which each input will use some number of them according to a function of …