"Tag" Finite State Machine

Discussion in 'HTML' started by Davide T, Dec 10, 2003.

  1. Davide T

    Davide T Guest

    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)?
     
    Davide T, Dec 10, 2003
    #1
    1. Advertising

  2. Davide T

    Eric Bohlman Guest

    "Davide T" <> wrote in
    news:br78ja$3ve4$-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.
     
    Eric Bohlman, Dec 10, 2003
    #2
    1. Advertising

  3. Davide T

    Davide T Guest

    "Eric Bohlman" <> wrote in message
    news:Xns944D5DFD05BBDebohlmanomsdevcom@130.133.1.4...
    > "Davide T" <> wrote in
    > news:br78ja$3ve4$-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?
     
    Davide T, Dec 10, 2003
    #3
  4. Davide T

    Andy Dingley Guest

    On Wed, 10 Dec 2003 13:56:26 -0000, "Davide T" <>
    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
     
    Andy Dingley, Dec 10, 2003
    #4
  5. In article <br78ja$3ve4$-berlin.de>,
    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
     
    Hywel Jenkins, Dec 10, 2003
    #5
  6. Davide T

    Eric Bohlman Guest

    "Davide T" <> wrote in
    news:br7db1$69o5$-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.
     
    Eric Bohlman, Dec 10, 2003
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. deejayfred
    Replies:
    0
    Views:
    565
    deejayfred
    Oct 2, 2003
  2. SomeDude
    Replies:
    3
    Views:
    3,181
    arant
    Aug 14, 2006
  3. Inderkal
    Replies:
    8
    Views:
    1,279
    rickman
    Dec 9, 2004
  4. Roberto Nunnari
    Replies:
    2
    Views:
    8,558
    Thomas Weidenfeller
    Feb 4, 2004
  5. Paul J. Lucas
    Replies:
    0
    Views:
    498
    Paul J. Lucas
    Sep 2, 2003
Loading...

Share This Page