Velocity Reviews > HTML > "Tag" Finite State Machine

# "Tag" Finite State Machine

Davide T
Guest
Posts: n/a

 12-10-2003
How would I illustrate a finite state machine that checks that each start
tag in an HTML document has a corresponding end tag (ignoring nested tags of
the same type and assuming that there is only a finite set of tags)?

Eric Bohlman
Guest
Posts: n/a

 12-10-2003
"Davide T" <(E-Mail Removed)> wrote in
news:br78ja\$3ve4\$(E-Mail Removed)-berlin.de:

> How would I illustrate a finite state machine that checks that each
> start tag in an HTML document has a corresponding end tag (ignoring
> nested tags of the same type and assuming that there is only a finite
> set of tags)?

Very awkwardly. Such a machine would need to have one state for every
possible combination of open tags; if N is the number of tags in HTML, then
under your constraints there would be N! states; with only 10 tags (there
are more than that), you'd have over 3 million possible states.

Davide T
Guest
Posts: n/a

 12-10-2003
"Eric Bohlman" <(E-Mail Removed)> wrote in message
news:Xns944D5DFD05BBDebohlmanomsdevcom@130.133.1.4 ...
> "Davide T" <(E-Mail Removed)> wrote in
> news:br78ja\$3ve4\$(E-Mail Removed)-berlin.de:
>
> > How would I illustrate a finite state machine that checks that each
> > start tag in an HTML document has a corresponding end tag (ignoring
> > nested tags of the same type and assuming that there is only a finite
> > set of tags)?

>
> Very awkwardly. Such a machine would need to have one state for every
> possible combination of open tags; if N is the number of tags in HTML,

then
> under your constraints there would be N! states; with only 10 tags (there
> are more than that), you'd have over 3 million possible states.

Right, well say there was only two tags... <head> and <body> - how would I
do it?

Andy Dingley
Guest
Posts: n/a

 12-10-2003
On Wed, 10 Dec 2003 13:56:26 -0000, "Davide T" <(E-Mail Removed)>
wrote:

>How would I illustrate a finite state machine that checks that each start
>tag in an HTML document has a corresponding end tag (ignoring nested tags of
>the same type and assuming that there is only a finite set of tags)?

Very easily, if you allow maintenance of some attributional state (ie
the name of the tag that opened the element), but otherwise impossible
in a FSM (trivial proof), unless you permit a truly huge number of
states and a limited length document.

Nesting tags of the same type makes no difference.

This just isn't an appropriate task for a classical FSM, but it's very
easily solved by something with a stack.

--
Die Gotterspammerung - Junkmail of the Gods

Hywel Jenkins
Guest
Posts: n/a

 12-10-2003
In article <br78ja\$3ve4\$(E-Mail Removed)-berlin.de>,
http://www.velocityreviews.com/forums/(E-Mail Removed) says...
> How would I illustrate a finite state machine that checks that each start
> tag in an HTML document has a corresponding end tag (ignoring nested tags of
> the same type and assuming that there is only a finite set of tags)?

Recursion.

--
Hywel I do not eat quiche
http://hyweljenkins.co.uk/
http://hyweljenkins.co.uk/mfaq.php

Eric Bohlman
Guest
Posts: n/a

 12-10-2003
"Davide T" <(E-Mail Removed)> wrote in
news:br7db1\$69o5\$(E-Mail Removed)-berlin.de:

> Right, well say there was only two tags... <head> and <body> - how
> would I do it?

Well, in that case you'd have three states: [empty],[<head>], and
[<head><body>] (assuming you required them to be in the correct order).
would have a transition back to [empty] on </head>, and a transition to
[<head><body>] on <body>. And so on.