14-05-2026, 05:21 PM
(13-05-2026, 09:58 PM)Jorge_Stolfi wrote: You are not allowed to view links. Register or Login to view.Without these sum constraints, the three parsing levels can be realized as compact finite automaton that can be drawn on a single page. With the sum constraints, the automaton is about 3x bigger because each state must be unfolded into three states in order to record the three counts in the part already parsed.
Oops. Actually it is more than 3x, because each state must keep track of the x+y count (0,1,2) and the q+d+e count (01,2); so each state near the end of the word may become 9 states. (The g+h count is checked immediately so it does not require duplicating states)
All the best, --stolfi

