W3C home > Mailing lists > Public > www-tag@w3.org > January 2012

Re: The Science of Insecurity

From: Bjoern Hoehrmann <derhoermi@gmx.net>
Date: Tue, 10 Jan 2012 16:20:36 +0100
To: Ivan Žužak <izuzak@gmail.com>
Cc: Henry Story <henry.story@bblfish.net>, "www-tag@w3.org List" <www-tag@w3.org>
Message-ID: <1eiog79al470ok02ggkf876mhcc20ctb28@hive.bjoern.hoehrmann.de>
* 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

This archive was generated by hypermail 2.3.1 : Wednesday, 7 January 2015 15:33:13 UTC