Results 1 to 4 of 4

Math Help - please help, context free language

  1. #1
    Newbie
    Joined
    Nov 2009
    From
    Canada, NWT
    Posts
    20

    please help, context free language

    In this question, we consider languages over the alphabet {0, 1,#}. If n is a positive integer,
    let B(n) be the binary representation of n (with no leading 0ís). For example, B(22) is the
    string 10110.
    Let L1 = {B(n)#B(m) : n,m 2 Z+ and n > m}. For example, 11000#10110 is in L1
    because B(24) = 11000 and B(22) = 10110 and 24 > 22. However, the strings 11000#111111
    and 10110#11000 are not in L1. L1 is not regular.
    Let L2 = {B(n)#(B(m))R : n,m 2 Z+ and n > m}. For example, 11000#01101 is in
    L2 because B(24) = 11000 and (B(22))R = (10110)R = 01101 and 24 > 22. However, the
    strings 11000#111111 and 10110#00011 are not in L2.
    (a) Is L1 context-free?
    (b) Is L2 context-free?
    If you answer yes for either language, you must give a context-free grammar for that
    language. You do not have to give a formal proof that the grammar generates the language,
    but you should give, for each variable in your grammar, a precise description of the set of
    strings that the variable generates.
    If you answer no for either language, you must give a formal proof that the language is
    not context-free.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    L_1=\{1u1vw\#1u0v'\mid u,v,v',w\in\{0,1\}^*,|v|=|v'|\}. That is, both numbers start with 1. Then comes the same (possibly empty) string. Then the first number has 1 while the second number has 0. After that, the first number has at least as many remaining digits as the second one.

    Since L_2=\{u\#v^R\mid u\#v\in L_1\}, we have that L_2=\{1u1vw\#v'^R0u^R1\mid u,v,v',w\in\{0,1\}^*,|v|=|v'|\}. This can be shown to be context-free similar to how \{u\#u^R\mid u\in\{0,1\}^*\} is context-free.

    That L1 is not context-free can be shown using the Pumping Lemma:
    If a language L is context-free, then there exists some integer p ≥ 1 such that any string s in L with |s| ≥ p (where p is a pumping length) can be written as

    s = uvxyz

    with substrings u, v, x, y and z, such that |vxy| ≤ p, |vy| ≥ 1, and

    u(v^n)x(y^n)z is in L for every integer n ≥ 0.
    Note that this version of the lemma guarantees that |vxy| ≤ p.

    Consider \{1^k0^k1\#1^k0^k0\mid k\in\mathbb{Z}^+\}\subset L_1. By the Pumping Lemma, there exists a p such that for all k > p, 1^k0^k1\#1^k0^k0=uvxyz, |vy|\ge1, |vxy|\le p and uv^nxy^nz\in L_1 for all n\ge0. One must consider all possible locations of vxy with respect to #. Obviously, v and y cannot contain #. Also, vxy cannot come before #: otherwise, dropping v and y (taking n = 0) will make the number before # have fewer digits than the one after #. Clearly, vxy cannot come after # because v and y can be pumped to make the second number greater that the first.

    This leaves the case where # is in x. Since |vxy| <= p and k > p, v is a substring of 0^k1 while y is a substring of 1^k. If |v| > |y|, then removing v and y (taking n = 0 above) makes the first number shorter than the second, so the result is not in L1. Therefore, |v| <= |y|. By doubling v and y (taking n = 2), we make the second number start with 1^{k'} where k' > k, and the new second number is at least as long as the new first one. This means the second number is greater, and so again the result is not in L1.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    From
    Canada, NWT
    Posts
    20
    how is { u # u^r } is context free?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    It is generated by the following grammar.

    S -> #
    S -> 1S1
    S -> 0S0
    Last edited by emakarov; December 6th 2010 at 08:28 AM. Reason: Replaced the empty word by #
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Context free language question.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 19th 2011, 01:02 AM
  2. context-free grammar
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 27th 2011, 11:51 AM
  3. context free languages
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 30th 2010, 06:11 PM
  4. context-free language and grammar
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: June 28th 2010, 04:42 PM
  5. context-free grammar
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 6th 2010, 09:26 PM

Search Tags


/mathhelpforum @mathhelpforum