"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. Advertisements

  2. Davide T

    Eric Bohlman Guest

    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. Advertisements

  3. Davide T

    Davide T Guest

    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

    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.
     
    Andy Dingley, Dec 10, 2003
    #4
  5. Recursion.
     
    Hywel Jenkins, Dec 10, 2003
    #5
  6. Davide T

    Eric Bohlman Guest

    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. Advertisements

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.