Search code examples
grammarformal-languages

Formal Languages - Grammar

I am taking a Formal Languages and Computability class and am having a little trouble understanding the concept of grammar. One of my assignment questions is this:

Take ∑ = {a,b}, and let na(w) and nb(w) denote the number of a's and b's in the string w, respectively. Then the grammar G with productions:

S -> SS
S -> λ
S -> aSb
S -> bSa

generates the language L = {w: na(w) = nb(w)}.

1) The language in the example contains an empty string. Modify the given grammar so that it generates L - {λ}.

  • I am thinking that I should modify the condition of L, something like:

    L = {w: na(w) = nb(w), na, nb > 0}

    That way, we indicate that the string is never empty.

2) Modify the grammar in the example so that it will generate L ∪ {anbn+1: n >= 0}.

  • I am not sure on how to do this one. Should that mean I make one more condition in the grammar, adding something like S -> aSbb?

Any explanation about these two questions would be greatly appreciated. I'm still trying to figure these grammar stuff out so I am not sure about my answers.

Solution

  • 1) The question is about modifying the grammar to obtain a new language; so don't modify directly the language…

    Your grammar generates the empty word because of the production:

    S -> λ

    So you could think of removing this production altogether. This yields the following grammar:

    S -> SS
S -> aSb
S -> bSa

    Unfortunately, this grammar doesn't generate a language (a bit like in induction, it misses an initial: there are no productions that only consist of terminals). To fix this, add the following productions:

    S -> ab
S -> ba

    2) Don't randomly try to add production rules in the hope that it's going to work. Here you want a's followed by b's. So the production rule

    S -> bSa

    must certainly disappear. Also, the rule

    S -> SS

    would produce, e.g., abab (try to see how this is obtained). So we'll have to remove it too. We're left with:

    S -> λ
S -> aSb

    Now this grammar generates:

    λ
ab
aabb
aaabbb

    etc. That's not bad at all! To get an extra trailing b, we could create a new non-terminal, say T, replace our current S by T, and add that trailing b in S:

    T -> λ
T -> aTb
S -> Tb

    I know that this is homework; I gave you the solutions to your homework: that's because, from the way you asked your question, it seems you're completely lost. I hope this answer will help you get on the right path!