Results 1 to 8 of 8

Math Help - Check this Grammer Please

  1. #1
    Junior Member
    Joined
    Nov 2008
    Posts
    36

    Check this Grammer Please

    The Question :
    Prove that the following languages are context-free by giving grammars that accept them.

    S = { 0^i 1^j 2^k 3^l | i=k and j=l }

    I felt like I could just substitute i = k and j = l, int the expression thus having to show that  0^k 1^l 2^k 3^l has some CFG.

    Is that enough? This is the result I got from doing that :

    Let T=
    A→1S2 | ϵ
    B→0B3 | A |ϵ
    Then the CFG that accepts S is T.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    What you have written does not make much sense to me. Can you show, for example, how you would generate 02 with your grammar ?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    Oops sorry about that. There was some typo. This is the grammar that I am proposing :

    S → B | ϵ
    A→1A2 | ϵ
    B→0B3 | A |ϵ

    So for example it could generate :

    B => 0B3 => 00B33 => 00A33 => 001A233 => 001233
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    That grammar is for 0^k1^l2^l3^k

    EDIT: Have you tried showing that the language is not context-free ?
    Last edited by Traveller; October 15th 2010 at 03:10 PM.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    I feel so stupid, this is the grammar its supposed to generate \{ 0^i1^j2^k3^\ell \mid \text{$i = \ell$ and $j = k$}\}
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    so i'm guessing it accepts the above set
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Yes, it does. How far did you proceed with i=k and j=l ?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Nov 2008
    Posts
    36
    Truthfully, I didn't bother because I am trying to get this homework completed. But I did try it a little, and it seems as
    if there is no CFG that recognizes that set. But thats just an intuition. I will try this for practice later, I guess. Thanks again.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: March 12th 2011, 04:05 AM
  2. Star Operator and Grammer
    Posted in the Advanced Math Topics Forum
    Replies: 6
    Last Post: September 20th 2010, 03:51 AM
  3. Can you check please
    Posted in the Statistics Forum
    Replies: 8
    Last Post: February 3rd 2010, 03:42 AM
  4. Somebody check if this is ok!
    Posted in the Calculus Forum
    Replies: 5
    Last Post: June 16th 2008, 09:02 AM
  5. grammer problem
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: April 29th 2008, 08:32 PM

Search Tags


/mathhelpforum @mathhelpforum