2
$\begingroup$

I'm new to the subject of automata theory. I get most of the stuff, but I cannot figure out when to change the state of the machine, and when to keep the state unchanged for a particular transition operation. An explanation would be appreciated. Thanks!

Also, my understanding of states is that they're basically the indicators in the machine, which let it know which operation is going on. Is this the correct analogy? If not, can you give a better one?

Edit: Regarding finite automata, I can understand when to change the state. But I'm confused in push down automata. Do you change the state only during push and pop, and during introduction of a new character? Or are there more reasons to change the state?

$\endgroup$

closed as unclear what you're asking by D.W., David Richerby, Rick Decker, lPlant, Nicholas Mancuso May 26 '15 at 0:13

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ How about finite automata? $\endgroup$ – Raphael Apr 11 '15 at 14:43
  • $\begingroup$ Why do you ask about push down automata? Why not about finite automata? $\endgroup$ – babou Apr 11 '15 at 19:21
  • $\begingroup$ If you do the standard PDA --> CFG --> PDA dance steps, you see that the PDA's state is not really required, as the result has one state only. PDAs have states more to keep them in line with other automata, e.g. as an extension of NFAs. $\endgroup$ – vonbrand Aug 5 '15 at 22:44
2
$\begingroup$

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 (a proof can be found here). The basic trick is to use the tape alphabet to encode the state of the original machine (and part of the transition). This works perfectly well for both deterministic and non-deterministic PDAs.

This is a little unsatisfying however, as a single state machine with a huge tape alphabet is not a particularly natural way to design a PDA (at least if you're like most humans I have met, there might be someone who thinks that way, if so, well done[!|?]). One intuitive reason to change state is as you suggest, because the machine is meant to be doing something different. Analogously to how we would talk about what we as humans are doing, for example, when we're working. We might break a task into steps, and perform them in a "sensible" sequence. The idea is the same with designing PDAs, break the recognition task into a series of steps, and change state when you move from one step to another.

As an example, consider the canonical non-regular context free language $\{a^{n}b^{n}\mid n\in\mathbb{N}\}$. In processing this language, we might have a starting state, a state for processing $a$s, a state for processing $b$s and an accept state. We move from the start state to the "$a$" state by pushing a botoom-of-the-stack symbol, then process the $a$s (probably by pushing a symbol for each $a$), then move to the "$b$" state using a $\varepsilon$-transistion, process the $b$s (popping off the symbols we put on for the $a$s), then move to the accept state if we have reached the end of the input and can see the bottom-of-the-stack symbol.

This is not the only way to build a PDA for this language, but the changing of states has a natural, intuitive meaning that is useful to us as humans in the design process (and for others trying to understand or implement it).

Unfortunately there's no simple "this is when to change states" rule. As the single state example shows, you can design things in a very arcane, incomprehensible manner, but they are still correct. Like a number of things in maths, CS and programming, you really have to just practice it a bit, look at other solutions and develop your own intuition. It is in many ways like programming (funnily enough) - there's lots of ways to solve a problem, only some are good ways, but there is at best only general guidelines to what to do when and where.

$\endgroup$
0
$\begingroup$

This is a tricky question because we know that a CFL is generated by at least one CFG. Exist an algorithm to generate a PDA(accepts by empty stack) from a CFG. This PDA has only one state $q_0$ and the transitions are:

$\forall a \in \Sigma: \delta(q_0,a,a)=\{(q_0,\epsilon)\}$

$\forall A \in N: (q_0,\alpha)\in \delta(q_0,\epsilon,A)$

Where $\alpha$ is the right side of a production rule of $A$(expanding non-terminal in the stack). So, answering your question I would say that from this perspective at least it is not necessary to change state of a PDA.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.