Thread: 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: .
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.

The following grammar (taken from these lecture notes — DOC file) converts a word into :




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.

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.

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'.

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.

Could you remind what a strictly non contracting grammar is?

Originally Posted by emakarov

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.

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.

Originally Posted by emakarov

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.

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

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.

OK, I have an idea. Suppose we want to generate . We can't produce the string because that would require removing B and E, which would reduce the string length. So, we can generate 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.

Wow, thanks heaps emakarov! I don't think I would have thought of doing it that way. Very nice solution!