Results 1 to 12 of 12

Math Help - Creating a PSG for a language

  1. #1
    Newbie
    Joined
    Jun 2011
    Posts
    20

    Creating a PSG for a language

    Hey all, this question seems impossible to me. So if anyone can help me out it would be hugely appreciated.

    The question is to create a PSG for the Language: L= { \{0^{2^n} : n \ge 0} \} .
    It can be a type 0 as that would be easiest.

    Then create a strictly non contracting grammar for L.

    Starting with a type 0 grammar to create the PSG would be easiest but I really can't get much done at all.

    Thanks in advance for any help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    The following grammar (taken from these lecture notes DOC file) converts a word B0^nE into 0^{2n}:

    B0\to 00B
    BE\to\varepsilon

    Using the same idea, it should be possible to have B and E at the beginning and the end, respectively, with zeros between them and to repeatedly send a nonterminal D from B to E so that D changes each 0 it encounters into 00.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jun 2011
    Posts
    20
    Thanks for the help emakarov. I should be able to produce something with that but it is not working. Sorry, I know I am a not good at this kind of stuff.
    Would you be able to help out a bit more?

    Thanks for your response.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    Consider the following rules.

    S -> B0E
    B -> BI
    I0 -> 00I
    IE -> E
    B -> B'
    B'0 -> 0B'
    B'E -> epsilon

    Suppose you generated B0...0E (in the beginning there is just one 0). At any time B can spawn a nonterminal I that can travel right through the string of 0's doubling every 0. When I hits E, it disappears. This way you can generate strings B0^{2^i}E. Now, to remove B and E, B can travel to the right and annihilate with E. However, to prevent B from producing I when it is in the middle of the string, we can change B into B'.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Jun 2011
    Posts
    20
    Wow, thanks emakarov. I now understand how my thinking was incorrect.

    So that is a type 0 grammar, how do I create a strictly non contracting grammar for L.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    Could you remind what a strictly non contracting grammar is?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Jun 2011
    Posts
    20
    Quote Originally Posted by emakarov View Post
    Could you remind what a strictly non contracting grammar is?
    A strictly non contracting grammar for L would mean it is a type 1+ making it context sensitive without the empty string. So I need to change the productions of the type 0 grammar that are contracting to non contracting. Context-sensitive grammar - Wikipedia, the free encyclopedia ||| http://en.wikipedia.org/wiki/Noncontracting_grammar

    But how is this done?

    Thanks for any help.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    This is still unclear. First, the article you linked to says that sometimes type-1 grammars have the requirement that the left-hand side of a rule is no longer than the right-hand side and sometimes they don't. Which is the case here? If there is such requirement, can the left- and right-hand sides be of the same length? What does the word "strictly" in the name mean?

    Further, there is a Wiki article specifically about noncontracting grammars, where the definition does not say it has to be a type-1. They generate the same languages as type-1, but the requirements on the shape of the rules are different. If the definition is as you say, it is somewhat strange that the requirement to be type-1 is not reflected in the name.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Jun 2011
    Posts
    20
    Quote Originally Posted by emakarov View Post
    This is still unclear. First, the article you linked to says that sometimes type-1 grammars have the requirement that the left-hand side of a rule is no longer than the right-hand side and sometimes they don't. Which is the case here? If there is such requirement, can the left- and right-hand sides be of the same length? What does the word "strictly" in the name mean?

    Further, there is a Wiki article specifically about noncontracting grammars, where the definition does not say it has to be a type-1. They generate the same languages as type-1, but the requirements on the shape of the rules are different. If the definition is as you say, it is somewhat strange that the requirement to be type-1 is not reflected in the name.
    Section 11.3 from here: http://samples.jbpub.com/97814496155...11_LinzSEC.pdf should help.

    Or section 3 from here: http://www.cs.ucr.edu/~jiang/cs215/tao-new.pdf

    I am not good at this and don't really understand type 1 grammars myself.
    I do believe that the left and right hand sides can be of the same length.

    The type 0 you provided has 1 contracting term from what I can see which is IE -> E. So that needs to be changed but I don't know how nor do I know what the strictly non contracting grammar for L would be.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    Interesting. The definition that I learned said the rules have to be of the form xAy -> xvy, the way the first link above discusses the rationale for Definition 11.4.

    In my rules above, it is easy to change IE -> E into I0E -> 00E. That is, instead of

    I00E -> 00I0E -> 0000IE -> 0000E

    we would have

    I00E -> 00I0E -> 0000E.

    However, I don't know how to get rid of the rule B'E -> epsilon.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785
    OK, I have an idea. Suppose we want to generate 0^{2^n}. We can't produce the string B0^{2^n}E because that would require removing B and E, which would reduce the string length. So, we can generate B0^{2^{n-1}}E and remove B and E during the last pass, when the number of 0's still grows. The last three rules in post #4 can be replaced with

    B -> B'
    B'0 -> 00B'
    B'00E -> 0000

    This produces strings of length 2^n for n >= 2, so S -> 0 and S -> 00 probably need to be added.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Jun 2011
    Posts
    20
    Wow, thanks heaps emakarov! I don't think I would have thought of doing it that way. Very nice solution!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. language of mathematics
    Posted in the Math Forum
    Replies: 1
    Last Post: November 10th 2011, 01:09 AM
  2. Language and proofs
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 8th 2009, 01:05 PM
  3. Language C ---matrix----
    Posted in the Math Software Forum
    Replies: 1
    Last Post: July 2nd 2008, 02:07 PM
  4. LaTeX and language
    Posted in the LaTeX Help Forum
    Replies: 2
    Last Post: October 18th 2007, 08:14 AM

Search Tags


/mathhelpforum @mathhelpforum