"Tag" Finite State Machine

Davide T · Dec 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 · Dec 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)?

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 · Dec 10, 2003

Eric Bohlman said:
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 · Dec 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)?

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.

Hywel Jenkins · Dec 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)?

Recursion.

Eric Bohlman · Dec 10, 2003

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.

VHDL finite state machine	11	Apr 27, 2009
finite state machine with enum	7	Feb 10, 2010
(Maybe off topic) Can someone explain what a finite state machine is?	3	Jul 19, 2011
Very simple finite automaton (?)	6	Sep 23, 2009
Is there a way to pass this state from component to the fetch?	1	Apr 24, 2023
Array to select/deselect based on boolean conditions	0	Apr 1, 2019
h tag problem	15	Apr 12, 2012
regexp finite state machine?	0	Mar 8, 2005

"Tag" Finite State Machine

Davide T

Eric Bohlman

Davide T

Andy Dingley

Hywel Jenkins

Eric Bohlman

Ask a Question

Similar Threads

Members online

Forum statistics

Latest Threads