[9 April 2012]

For a while it has seemed to me interesting and potentially useful that any context-free language L can be approximated by regular languages which accept either a subset or a superset of L. (See earlier posts from 2008 and 2009.)

Apart from the intrinsic interest of the fact, this means that it’s possible in principle to define XSD simple types using those regular approximation languages, which in turn means it’s possible to use XSD validation to catch at least some syntactic errors in strings which should be members of L.

Some time ago, I had occasion to translate the ABNF of RFC 3986 and RFC 3987 into XSD regular expressions (possible in that case without an approximation, since the languages defined by those to RFCs are all regular). The mechanism I used was simple: each ABNF production turned into an entity declaration, and each non-terminal on the right-hand side of a rule turned into an entity reference.

Today I was reviewing that work and it occurred to me that if we could find a regular approximation by algebraic manipulation of the grammar (without any detour through finite-state automata), it would make it much simpler to write the necessary XSD patterns.

But how?

Given a context-free grammar for L, can we identify algebraic rules which would allow us to derive a regular grammar for a regular approximation to L?