I think the commenters are gracious for not having down-voted my question. It seemed I was lazy. But I was lazy no more. The last two days I have put my head into this matter and I just finished the implementation and verified it against the textbook example.
Of all the texts and presentations I could find I found these lecture notes the best:
What had confused me in the past was all that theoretical talk about "item" and "item set". Also this dot notation seemed weird.
But what helped me was actually doing it all (in SQL) where it is clear that one production on the RHS has a sequence, and so we have a production id and a sequence number to get to exactly one RHS symbol (non-terminal or terminal). So what an "item" really is is one RHS symbol of one production, at least if we terminate the RHS symbols with one (implicit) termination, i.e., even though the rule:
E : E "+" T has only 3 RHS symbols, a position 4 is valid and indicates the end of the production.
Then thanks to these lecture notes above for going directly from "item" to "state" and even including the transitions immediately in the picture (and for having a picture in the first place).
So, the approach in a nutshell is this:
- Add a single trivial start symbol to the grammar if needed, so that if the real start symbol has multiple productions, there will be only one production for the top-level start symbol.
- Think of the productions as a relation: PROD(P#, LHS, SEQ#, RHS), these tuples are all "items" (for lack of a better word), example
- For ease of use complete the Production by adding a terminal item to each, this is so that if you ask for the next step by increasing to the next RHS symbol, you can find the final one which just has nil RHS symbol.
- Now magically the State Transition network emerges simply from the following actions.
Why that initial trivial start symbol is required can be seen with the standard example:
E : T
E : E "+" T
T : F
T : T "*" F
F : n
F : "(" E ")"
If you don't add
E' = E then there is not one top level symbol. You could start at E but you can also start at T or at F. You just don't know where to start!
- Create your first state (S0) with that trivial single start symbol production's first RHS (also trivially the original start symbol)
- Now for that one RHS symbol of the start symbol, add more member items into the state by taking the first RHS symbol (item) of all productions with LHS being that initial RHS symbol of S0
- Now do the same for all items you have added, and recursively until nothing new is added (this is the transitive closure of LHS -> RHS tuples).
I found it helpful to think of these items as individual PROD(P#,LHS,SEQ#,RHS) tuples. It's not that you need to write out the full
LHS : RHS1 RHS2 RHS3 ... line and put a dot somewhere.
- For each item in your completed state, make a list of unique RHS symbols
- For each such unique RHS symbols, find all member items in your state that have that unique RHS symbol. (Remember an item is just one position on the RHS of a production, it's not a line of text with a dot somewhere. So there is only one RHS symbol (or nil) in any item, therefore there is no question about the RHS symbols have a dot before them or not.)
- Now each of these (groups of) member items from your current state for the same unique RHS form a new state.
- Each new state is defined by the next step in the production PROD(P#,LHS, ++SEQ#, RHS').
- Regardless if RHS' is something or nil, each group of such production steps coming from one unique RHS identify one state.
- You might have already seen that state before, check if you find one with the same definition items, if so, use that existing state, if not, make a new state.
- For all new states, generate the closure by again going to the start RHS symbol of each production for the item that defines the state, and from there recursively for each item you just included (closure)
- Continue for all such unique RHS symbols, for all previously generated states.
- Note: the transitions come right out of this procedure, whether the state already existed, or you just created a new one, the transition from the current member item of your current state becomes a next state.
- There is at most one transition from each member item of a state
- Multiple member items of a state may have the same new state
- The RHS of each member items of the state are the event which triggers the transition (at least the terminal symbols are.)
So at the end of this process of unique RHS, state member for that RHS, next SEQ# of the RHS sequence of the production, merging states that already exist, and then complete the closure again, and recording the new state for each state member item, magically the entire finite state automaton has been defined.
Is this explanation shorter and more concise or intelligible as all he outstanding CS lectures and text books and lecture notes? Probably not. But it is concise enough to promise that the state transition network comes out of this one procedure right from the productions of the grammar.