Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > HTML > "Tag" Finite State Machine

Reply
Thread Tools

"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)?


 
Reply With Quote
 
 
 
 
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.
 
Reply With Quote
 
 
 
 
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?


 
Reply With Quote
 
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
 
Reply With Quote
 
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
 
Reply With Quote
 
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).
[empty] would have a transition to [<head>] on a <head> tag. [<head>]
would have a transition back to [empty] on </head>, and a transition to
[<head><body>] on <body>. And so on.
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Safe finite state machine design SomeDude VHDL 3 08-14-2006 12:47 PM
Gate Level model of a Finite state machine Inderkal VHDL 8 12-09-2004 11:17 PM
FSM (Finite State Machine) Generator - Open Source Roberto Nunnari Java 2 02-04-2004 07:16 AM
HELP PLEASE!! - Finite State Machine - Automaton - Microprogrammed System deejayfred VHDL 0 10-02-2003 01:23 AM
ANNOUNCE: Hierarchical finite state machine system Paul J. Lucas C++ 0 09-02-2003 03:15 PM



Advertisments