Results 1 to 9 of 9

Math Help - Context Free Grammars - nobody was able to answer

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    6

    Context Free Grammars - nobody was able to answer

    Hey people,

    Had these few questions come up today and no one in the tut class could answer them, just curious on what the answers are or how u work them out.

    Find context-free grammars for the following languages:

    (a)

    L = {w : w ε {a, e}* and nₐ(w) = nₑ(w)} where nᵢ(w) is the number of i's in string w (i is a or e)


    (b)

    L = {w : w ε {a, e}* and nₐ(w) ≠ nₑ(w)} where nᵢ(w) is the number of i's in string w (i is a or e)


    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    115
    Quote Originally Posted by hekticity View Post
    Hey people,

    Had these few questions come up today and no one in the tut class could answer them, just curious on what the answers are or how u work them out.

    Find context-free grammars for the following languages:

    (a)

    L = {w : w ε {a, e}* and nₐ(w) = nₑ(w)} where nᵢ(w) is the number of i's in string w (i is a or e)


    (b)

    L = {w : w ε {a, e}* and nₐ(w) ≠ nₑ(w)} where nᵢ(w) is the number of i's in string w (i is a or e)


    If I understand you correctly, the first language contains the words with the same number of occurrences of a's and e's; in b these numbers are different.

    I would try something like this (I guess you can try to simplify it):
    S->aE|Ea|eA|Ae| \varepsilon
    E->eS|Se|EaE|aEE|EEa
    A->aS|Sa|AeA|eAA|AAe

    The basic idea is that whatever word you can derive from A, it will have one more a then e. The hard part is to prove that this can generate all words. (That's why I suggested that you should first think about simplifying this grammar.)

    IMHO you can solve the part b in a similar fashion.
    First you decide that you have say 4 more e's than a's.
    You start like S => S1, where S1 is a symbol from which you can generate only words with more e's then a's. You do several steps to obtain something like S2eS2eS2eS2eS2 and then apply the rules for S2. You have to make the rules for S2 in a such way, that S2 generates only words with the same number of both symbols. (Again, you can try to simplify this or to make a completely different grammar, but the basic idea I gave you above should help you.)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by hekticity View Post
    Hey people,

    Had these few questions come up today and no one in the tut class could answer them, just curious on what the answers are or how u work them out.

    Find context-free grammars for the following languages:

    (a)

    L = {w : w ε {a, e}* and nₐ(w) = nₑ(w)} where nᵢ(w) is the number of i's in string w (i is a or e)


    (b)

    L = {w : w ε {a, e}* and nₐ(w) ≠ nₑ(w)} where nᵢ(w) is the number of i's in string w (i is a or e)


    For part (a) I think this would also work

    S -> eaS | eSa | Sea | aeS | aSe | Sae | \varepsilon

    I have limited experience with these so someone please correct me if I'm wrong.

    Edit: By the way, part (b) is Example 6 in this article on Wikipedia.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    115
    Quote Originally Posted by undefined View Post
    For part (a) I think this would also work

    S -> eaS | eSa | Sea | aeS | aSe | Sae | \varepsilon

    I have limited experience with these so someone please correct me if I'm wrong.

    Edit: By the way, part (b) is Example 6 in this article on Wikipedia.
    I do not see how you get the word eeaaaaee. But I might have overlooked something. (I am not an expert in this area, either. I had some basic course on formal languages and automata - it was quite a long time ago.)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by kompik View Post
    I do not see how you get the word eeaaaaee. But I might have overlooked something. (I am not an expert in this area, either. I had some basic course on formal languages and automata - it was quite a long time ago.)
    You're probably right. I'm wondering what language my grammar describes, then.

    Edit: You're definitely right. It's pretty easy to see that the only non-empty strings possible either begin or end with ea or ae, or begin with an e and end with an a, or begin with an a and end with an e.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Actually, Example 6 in the previously referenced Wikipedia article says that "...the nonterminal T can generate all strings with the same number of a's as b's...."

    Do I understand correctly that

    S -> aSbS | bSaS | \varepsilon

    is a solution to part (a)?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    115
    Quote Originally Posted by undefined View Post
    Actually, Example 6 in the previously referenced Wikipedia article says that "...the nonterminal T can generate all strings with the same number of a's as b's...."

    Do I understand correctly that

    S -> aSbS | bSaS | \varepsilon

    is a solution to part (a)?
    Yes, you're right. And this solution is much better than mine, since it is very easy to show that this grammar generates L.

    Obviously, by induction you can show that each sentential form (anything you can derive from S) has as many a's as b's.

    By induction on n we show next, that if a word w consists of n a's and n b's, then there is a derivation for it.

    n=0,1 is easy.

    Inductive step: Suppose that n_a(w)=n_b(w)=n.
    Let w=a_1a_2\dots a_{2n}
    W.l.o.g., let w starts with a letter a, i.e., a_1=a.
    Let k be smallest number such that the count of a's and b's in a_1a_2\dots a_k is the same. (Since this is true for k=2n, such k exists.)
    Clearly, a_k=b. (Otherwise k cannot be minimal.)

    So, w can be rewritten in the form
    w=aw_1bw_2,
    where both w_1 and w_2 belong to L(G), i.e., they can be derived from S (by inductive hypothesis).

    A derivation for goes like: S\Rightarrow aSbS\Rightarrow^* aw_1bS \Rightarrow^* aw_1bw_2.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie
    Joined
    May 2010
    Posts
    6
    Thankyou very much both of you..


    so what is the answer to (A) (what exactly is the answer??)? Undefined's response or kompik?

    Any ideas on (B)?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Mar 2010
    From
    Bratislava
    Posts
    115
    Quote Originally Posted by hekticity View Post
    Thankyou very much both of you..


    so what is the answer to (A) (what exactly is the answer??)? Undefined's response or kompik?

    Any ideas on (B)?
    If you read this thread carefully, you must notice that you were given answers to both parts and for (A) we have also sketched a proof that the answer is correct.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. context-free grammar
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 27th 2011, 11:51 AM
  2. please help, context free language
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 6th 2010, 08:27 AM
  3. context free languages
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 30th 2010, 06:11 PM
  4. Context-free grammar
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: June 29th 2010, 09:41 AM
  5. context-free grammar
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 6th 2010, 09:26 PM

Search Tags


/mathhelpforum @mathhelpforum