some newbie formal language questions

From: confused (mathgeek42_at_hotmail.com)
Date: 05/23/04

  • Next message: Sabyasachi Basu: "Recursive solution to the LCS problem." 
    Date: Sun, 23 May 2004 14:27:39 -0400

    hey guys,

    If I'm asked to show a CFG for the language

    L = {a^ib^ja^jb^i| i = 0, 1, ..., j = 0, 1, ...}

    [question #1] does the following grammar work?

    G = { {S }, {a, b}, S, see below for rewrite rules}

    S-> lambda S-> bSa
    S->X X->aXb X-> lambda

    [question #2] in particular, is my use of S-> lambda
    and X-> lambda as rewrite rules ok? would the string:
    a^0b^2a^2b^0 could be generated by the following rules:
    S->bSa, S->bSa, S->X, X->lambda ?

    [question #3] assuming #1 is yes; can G be improved
    upon?

    [question #4] If a word is a^iXb^i, and there is a rewrite
    rule, X-> lambda, then does that production essentially
    terminate the derivation (I think so, but checking...)?
    so if we apply X->lambda to a^iXb^i it now becomes
    a^ib^i, is this common? The reason I ask, is because
    although I think this seems right, none of the examples
    in my book so far, use a rewrite rule to lambda, to
    terminate a derivation.

    Notation:
    a^i i repetitions of a.
    lamda = empty word
    non-terminals in caps
    terminals in undercase.

    Thanks.

  • Next message: Sabyasachi Basu: "Recursive solution to the LCS problem."