Parsers Progress – Convergence

[Rescued from the old blog – Thanks to Damian]

The algorithm and data structure are designed to build a near optimal deterministic finite state automata for a regular language with a single pass, unlike the current three pass ‘Thompson Process’.

But even I was shocked when it spat this DFA out for the regular language (‘A’ | ‘A’ ‘B’) ‘D’.

DFA encapsulated NFA for (‘A’ | ‘A’ ‘B’) ‘D’.

(‘A’ | ‘A’ ‘B’) ‘D’ can also be expressed as ‘A’ [‘B’] ‘D’ – and it is this reduction that has been built.

If I was to take the constructed DFA and convert it back into a regular language I would in effect get the simplified ‘A’ [‘B’] ‘D’

Instead of being slightly more split worldpath wise, the convergence really seems to be very strict.

The cardinal semantics of the state group is slightly different than I expected. The second state clearly contains three states, one of which is mutually exclusive to the other two – it essentially describes the ‘states that you may be at this group state for’. I will try a thought experiment and try and work out if I can maintain a strict meaning of

About James McParlane

CTO Massive Interactive. Ex Computer Whiz Kid - Now Grumpy Old Guru.
This entry was posted in MetaWrap Server, Parsing Theory. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s