Re: CFG

lizzie <lizzie@xxxxxxxxxx> wrote:
I have already solved the grammar for a^ib^jc^k|i+j=k, as:
S -> Epsilon|aSc|B
B->bBc|Epsilon

That will generate a language such as abcc.

However, I am trying to find a grammar for a^ib^jc^k|j>=i+k-3.

S -> Abbb|bbbC|Epsilon
A ->ab|Epsilon
C ->cb|Epsilon

will make it so that j=i+k-3, but I can't figure out how to combine
abc and still keep the order.

It's probably easier to find a pushdown automaton for this language.
But I'll give the grammar a try:

S -> AC | aAC | aaAC | aaaAC | ACc | aACc | aaACc | ACcc | aACcc | ACccc
A -> aAb | Ab | eps
C -> bCc | bC | eps

C derives all strings b^j c^k for which j >= k. A derives all strings
a^i b^j for which j >= i. AC thus derives all a^i b^j c^k for which j
= i+k. The garbage rules for S deal with the "-3" part.

Tor Myklebust
.

Relevant Pages

  • Re: add support for other languages
    ... language DLLs or a single DLL with multiple language support, ... Just compile in Unicode ... You can create a hand-edited resource that contains Unicode strings, but you have to do it ... I don't know where is the language support comes into ...
    (microsoft.public.vc.mfc)
  • Re: Two Questions about "strlen", "strcat" and "strcpy"
    ... >>Important is that we have in the standard language a way of using ... > No. zero terminated strings is the whole problem in the first place. ... > programmer to think in terms of implementation and constantly respin ... The standards comitee refuses any change, ...
    (comp.lang.c)
  • Re: GNU gettext
    ... The gettext documentation explains how the keys work. ... translation files, or that you'd need to write a small utility to help ... gettext was desined for plain C, the keys are C strings ... as a developer you have no clue what every language ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: How come Ada isnt more popular?
    ... A language with a Hinldey-Milner type system ... fixed size strings, unbounded strings, suffix tree. ... container varies, the element does not. ...
    (comp.lang.ada)
  • Re: Substituting the main menu bar(s)
    ... I have tab-separated-value table of strings maintained with Excel, with a column for each language. ... All it does is replace the strings according to the translation table. ... I also have a batch file which calls the translation app, and then invokes the compiler on each resource-only DLL project. ...
    (microsoft.public.vc.mfc)