Re: The Science of Insecurity

* Ivan Žužak wrote:
>Sorry for being nitpicky or if I have misunderstood you. The reason
>why no such generic tools exist is that such tools are impossible to
>create. As far as I can remember, ABNF/BNF/EBNF are used to define
>context-free grammars (CFG) and express context-free languages, which
>are a superset of regular languages. Therefore, there is no way to
>construct a DFA from an arbitrary CFG (however, it is possible to
>create a DFA from a CFG which expresses a regular language).

The practical example was deciding whether URI schemes match the generic
syntax. The generic syntax is a regular language, and most schemes are
either regular or sufficiently simple that you can quite easily find any
problems with them in this manner. If you rewrite any y^n z^n into the
regular y* z* then the resulting language is a regular superset and if
that is a subset of URI syntax then so is the non-regular context-free
subset. If not, you can generate examples and check whether they are in
the non-regular language until the end of time, or maybe you are lucky
and the machine halts, or you get bored after a while and halt it your-
self without an answer even though there might be one. The point was, as
it is, none of these options are easily accessible.
-- 
Björn Höhrmann · mailto:bjoern@hoehrmann.de · http://bjoern.hoehrmann.de
Am Badedeich 7 · Telefon: +49(0)160/4415681 · http://www.bjoernsworld.de
25899 Dagebüll · PGP Pub. KeyID: 0xA4357E78 · http://www.websitedev.de/

Received on Tuesday, 10 January 2012 15:21:03 UTC