> From: Raul Miller <[email protected]>
>
> On Thu, Oct 8, 2009 at 12:27 PM, Oleg Kobchenko wrote:
> > That's why it's called "finite". But when you need
> > a stack or when you have arbitrary combinations
> > "[(", "[((",..."[(((((((((",... etc,
> > they are not finite.
>
> That's...
>
> That would be correct if the input sequence could be
> infinite in length. However, formal treatement of push
> down automata seems to require that the input
> sequence be finite.
>
> So, personally, I would not characterize pushdown
> automata as not being finite.
It was good to point that out. However, the problem is not
the length of the input. What I illustrated is the length
of a production, which is really infinite. However a production
can be infinite in FSA-covered grammar (e.g. a J name). Whereas
the term "finite" in both FSA and PDA refers to possible states.
Where they differ is in the presence of stack in PDA. Grammar-wise
FSA represents a regular grammar, whereas PDA handles
context-free grammars, which is required for the task at hand.
It should be possible to have a generic PDA working similarly to
FSA as implemented in dyadic ;: .
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
