X-Mozilla-Status: 0001 X-Mozilla-Status2: 00000000 Delivered-To: barryleiba.mailing.lists@gmail.com Received: by 10.58.170.71 with SMTP id ak7csp49263vec; Fri, 1 Nov 2013 16:02:52 -0700 (PDT) X-Received: by 10.68.135.100 with SMTP id pr4mr5531258pbb.62.1383346971923; Fri, 01 Nov 2013 16:02:51 -0700 (PDT) Return-Path: Received: from mail.ietf.org (mail.ietf.org. [2001:1890:123a::1:1e]) by mx.google.com with ESMTP id ud7si5861014pac.323.2013.11.01.16.02.51 for ; Fri, 01 Nov 2013 16:02:51 -0700 (PDT) Received-SPF: pass (google.com: domain of abnf-discuss-bounces@ietf.org designates 2001:1890:123a::1:1e as permitted sender) client-ip=2001:1890:123a::1:1e; Authentication-Results: mx.google.com; spf=pass (google.com: domain of abnf-discuss-bounces@ietf.org designates 2001:1890:123a::1:1e as permitted sender) smtp.mail=abnf-discuss-bounces@ietf.org; dkim=pass header.i=@ietf.org Received: from ietfa.amsl.com (localhost [IPv6:::1]) by ietfa.amsl.com (Postfix) with ESMTP id A3F2311E8153; Fri, 1 Nov 2013 16:02:50 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=ietf.org; s=ietf1; t=1383346970; bh=AjzgNlBQ3wrdI26qJjodkIabM1i5Vq7Gb7Nhznx6+Eg=; h=From:To:Date:Message-ID:References:In-Reply-To:MIME-Version:Cc: Subject:List-Id:List-Unsubscribe:List-Archive:List-Post:List-Help: List-Subscribe:Content-Type:Content-Transfer-Encoding:Sender; b=T8mvgwvGeQuZJF6/WvBEDa8q8XGKbLHOV9KNN/B/wDXuZkqGnhAnXoDGKW4GTacQk /LVnZ9vRg7E4rAUgnJAMPtYWNQKjdV6KaJdPPUdhu6HacLHCgpZJH2mbXzmwsMxrL0 a0X6aLrSJxczj2VuiTpnfUSorRCFGfhna9RMOEdw= X-Original-To: abnf-discuss@ietfa.amsl.com Delivered-To: abnf-discuss@ietfa.amsl.com Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id AA8D911E814C for ; Fri, 1 Nov 2013 16:02:48 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.714 X-Spam-Level: X-Spam-Status: No, score=-2.714 tagged_above=-999 required=5 tests=[AWL=-0.115, BAYES_00=-2.599] Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id zAJuaKRT1YQ6 for ; Fri, 1 Nov 2013 16:02:44 -0700 (PDT) Received: from mout.gmx.net (mout.gmx.net [212.227.17.20]) by ietfa.amsl.com (Postfix) with ESMTP id 2192D11E80E9 for ; Fri, 1 Nov 2013 16:02:43 -0700 (PDT) Received: from netb.Speedport_W_700V ([91.35.0.177]) by mail.gmx.com (mrgmx101) with ESMTPA (Nemesis) id 0LeRKD-1Vzqzn3Z9R-00q8pF for ; Sat, 02 Nov 2013 00:02:43 +0100 From: Bjoern Hoehrmann To: Bjoern Hoehrmann Date: Sat, 02 Nov 2013 00:02:46 +0100 Message-ID: References: <52717320.4000704@nostrum.com> <52733E23.2050103@alvestrand.no> In-Reply-To: X-Mailer: Forte Agent 3.3/32.846 MIME-Version: 1.0 X-Provags-ID: V03:K0:kMbdQW9zSdsIKgS8oZvy84+nBwRYb7t1j+Y/mh54eMuRMkP1J8D TakT/n9SE/pZo5pVcjR8eQD5dwwJb5xkUSP2hscKwjUq6eau9I3c1ATFs41v1ylIqH993hu NSSGI/09RI5Ls3o8E2cqTuGKEUc8BM1RrfHoFIIouaMj2Ax/uG4lwVm/AV0mG40IOQaUgE1 T92Y3gWm6yi9SsTMCgRMg== Cc: abnf-discuss@ietf.org Subject: Re: [abnf-discuss] addIceCandidate behavior X-BeenThere: abnf-discuss@ietf.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: "General discussion about tools, activities and capabilities involving the ABNF meta-language" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable Sender: abnf-discuss-bounces@ietf.org Errors-To: abnf-discuss-bounces@ietf.org * Bjoern Hoehrmann wrote: >Hmm doing the search right now I see "The Equivalent Conversion between >Regular Grammar and Finite Automata" by Jielan Zhang & Zhongsheng Qian, >published this year, that looks useful (that's #11 for 'nfa from regular >grammar', the first ten results do not look relevant to the query). Also >http://www.cs.um.edu.mt/gordon.pace/Research/Software/Relic/Transformation= s/RG/toFSA.html I had a chance to take a closer look at these and both fail to address a case where the context-free grammar defines a regular language but mixes left und right regular rules which I have found to be the hardest piece of the problem. The only solution I have seen so far consists of doing 1. Transform grammar into a simple form that allows you to apply the standard algorithms for the following problems. 2. Transform the grammar to remove indirect left recursion. 3. Transform the grammar to remove direct left recursion. 4. Apply a suitable algorithm for right regular grammars. This probably includes turning repetition in the grammar into expanded and recursive rules which is probably the most damaging operation if you want to mostly preserve the structure of the original grammar, at least I have never seen a proper proof that you can keep them intact (consider the epsilon removal if you want to keep zero-or-more repetitions)... -- = Bj=F6rn H=F6hrmann =B7 mailto:bjoern@hoehrmann.de =B7 http://bjoern.hoehrma= nn.de Am Badedeich 7 =B7 Telefon: +49(0)160/4415681 =B7 http://www.bjoernsworld.de 25899 Dageb=FCll =B7 PGP Pub. KeyID: 0xA4357E78 =B7 http://www.websitedev.d= e/ = _______________________________________________ abnf-discuss mailing list abnf-discuss@ietf.org https://www.ietf.org/mailman/listinfo/abnf-discuss