Talk:Tiki forum archive/Forum 5/7912
Source: 2013 Tiki forum 5, thread #7912. Original authors, UTC times, post IDs, and reply-parent IDs are preserved. This is an archive, not an active article discussion.
CFG prize challenge question
CFG prize challenge question
pdf23ds · 2009-02-08 21:39 UTC · Tiki post #7912
elidable terminators without a blowup in productions. I'd like to verify that the formalism I'm using is satisfactory to the judges.
The set of valid phrases to be parsed, P, is a set of lists of tokens. There are two types of tokens: start and terminator. Each token is paired with a number identifying the type of phrase it starts or terminates. The terminator is also paired with a boolean value indicating whether it is elided. (This, rather than simply leaving out the terminator token for elided ones, makes constructing the set much easier.) Tokens are written as tuples in angle brackets.
MapPhPh is a function that maps a phrase identifier (natural number) to a set of phrase identifiers. The returned identifiers are exactly those allowed to be nested under the passed in phrase in the grammar.
The contents of P is defined as follows.
For some natural x and bool y, [<Start x>, <Trm x y>] is in P. (y is whether the terminator is elided.)
Adjacent phrases: If p is in P, - and at some position pos in p two successive tokens are terminators of the form <Trm aID el1>, <Trm oID el2> (read "adjacent ID", "outer ID"), - and some number newID is a member of mapPhPh(oID), - and and for the list p_1 consisting of the first pos members of p, the boolean function canAppend(p_1, newID) is true (canAppend is defined below), - then for some bool elided, the list formed by inserting <Start newID>, <Terminator newID elided> into p at (pos + 1) is in P.
Nested phrases: If p is in P, - and for some number pos > 0, every token at or after position pos in p is a terminator, - and the two successive tokens at (pos - 1) in p are of the form <Start oldID>, <Trm oldID oldEl>, - and for some number newID, newID is a member of mapPhPh(oldID) - then p with <Start newID>, <Trm newID, newEl> inserted at pos is a member of P.
Not done yet!
canAppend(p, pID): Let lastEl be the last element of the list p. If lastEl is a start token, canAppend is true. Let p_1 be p without its last element. If lastEl is a terminator of the form <Trm tid el>, canAppend is true iff: - pID is a member of mapPhPh(tid) - and either el is false or canAppend(p_1, pID) is true.
That's it. I *think* that represents the salient aspects of phrases with elidable terminators in Lojban. The reason I don't have a token for the contents of phrases is that I think they're adequately represented by a Start and Trm token where the Trm is never elided and it has no contents itself. phrases that always have non-elided terminators. By the way, I'm using the Isabelle system to formulate this (the above is a semi-formal version of the completely formal version I've written), and I've done a few proofs that show that some of the desired properties hold (actually just constructing specific token lists and proving they're in P), so my description ought to be completely rigorous and consistent, even if it doesn't correctly model lojban's phrases.
Chris Capel -- "What is it like to be a bat? What is it like to bat a bee? What is it like to be a bee being batted? What is it like to be a batted bee?" -- The Mind's I (Hofstadter, Dennet)
To unsubscribe from this list, send mail to [email protected]
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
CFG prize challenge question
pdf23ds · 2009-02-08 22:04 UTC · Tiki post #7913 · reply to Tiki post #7912
> Adjacent phrases: If p is in P, > - and at some position pos in p two successive tokens are terminators > of the form <Trm aID el1>, <Trm oID el2> (read "adjacent ID", "outer > ID"), > - and some number newID is a member of mapPhPh(oID), > - and and for the list p_1 consisting of the first pos members of p,
I believe this should be "the first (pos + 1)" members of p.
Chris Capel -- "What is it like to be a bat? What is it like to bat a bee? What is it like to be a bee being batted? What is it like to be a batted bee?" -- The Mind's I (Hofstadter, Dennet)
To unsubscribe from this list, send mail to [email protected]
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
CFG prize challenge question
pdf23ds · 2009-02-09 02:18 UTC · Tiki post #7914 · reply to Tiki post #7912
> Not done yet! > > canAppend(p, pID): > Let lastEl be the last element of the list p. > If lastEl is a start token, canAppend is true. > Let p_1 be p without its last element. > If lastEl is a terminator of the form <Trm tid el>, canAppend is true iff: > - pID is a member of mapPhPh(tid) > - and either el is false or canAppend(p_1, pID) is true.
This should really be - either el is false, or - pID is a member of mapPhPh(tid) and canAppend(p_1, pID) is true.
Chris Capel -- "What is it like to be a bat? What is it like to bat a bee? What is it like to be a bee being batted? What is it like to be a batted bee?" -- The Mind's I (Hofstadter, Dennet)
To unsubscribe from this list, send mail to [email protected]
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
CFG prize challenge question
Jorge Llambías <[email protected]> · 2009-02-09 23:41 UTC · Tiki post #7923 · reply to Tiki post #7912
> I'm currently trying to prove that a CFG can't parse grammars with > elidable terminators without a blowup in productions.
By "blowup" you mean the number of rules increases exponentially with the number of terminators, right? I don't think that can be proven in general for grammars with elidable terminators, you need the kind of recursiveness that the Lojban grammar has for the exponential blowup to happen. Trivial counterexample:
text = A1 /T1/ | A2 /T2/ | ... | An /Tn/
That grammar has n rules, with n terminators. If the terminators are made elidable, we only have an increase to 2n rules.
> I'd like to > verify that the formalism I'm using is satisfactory to the judges.
I'm not one of the judges, but I'm interested, so I have some questions.
> The set of valid phrases to be parsed, P, is a set of lists of tokens.
First question: Do I understand correctly that a phrase is something like "KOhA BRODA LE BRODA KU VAU"?
The number of valid (and finite) such phrases with non-elidable terminators is countably infinite, and so is the number with elidable terminators. There is no blowup there. It is the number of rules, things like "sumti = LE selbri KU", which is finite, that probably blows up.
Or is a phrase something like "LE selbri KU", where "selbri" is one of its tokens? Is "GI NAI" a phrase? It is not by itself "valid" as in a valid text to be parsed, but there is a rule "gik = GI NAI".
> There are two types of tokens: start and terminator. Each token is > paired with a number identifying the type of phrase it starts or > terminates.
What are the types of phrases? Can you give some examples of tokens, some examples of phrases, and some examples of types of phrases?
I think I'm confused enough at this point, so I'll wait for the answers before proceeding. :)
mu'o mi'e xorxes
To unsubscribe from this list, send mail to [email protected]
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
CFG prize challenge question
pdf23ds · 2009-02-10 00:43 UTC · Tiki post #7927 · reply to Tiki post #7912
> On Sun, Feb 8, 2009 at 6:36 PM, Chris Capel <[email protected]> wrote: >> I'm currently trying to prove that a CFG can't parse grammars with >> elidable terminators without a blowup in productions. > > By "blowup" you mean the number of rules increases exponentially with > the number of terminators, right?
Well, more like with the number of allowable parent-child phrase relationships. E.g., you can nest a sumti in a selbri, so that's one. You can put a selbri in a bridi, so that's two. You can put a TO-TOI in lots of places, so that's like ten more. Etc. And I don't assert that the blowup is exponential--I'd sooner believe it's polynomial. But either way I'm really not to sure how to go about *proving* it.
>> The set of valid phrases to be parsed, P, is a set of lists of tokens. > > First question: Do I understand correctly that a phrase is something > like "KOhA BRODA LE BRODA KU VAU"?
Well, I'm thinking more abstractly. I don't think KOhA has a terminator, so I'm just assuming that kind of word is irrelevant. And I'm representing all terminators, so I think you'd need "BRODA LE BRODA VAU KU VAU". But that's basically it.
> The number of valid (and finite) such phrases with non-elidable > terminators is countably infinite, and so is the number with elidable > terminators. There is no blowup there. It is the number of rules, > things like "sumti = LE selbri KU", which is finite, that probably > blows up.
That's the idea.
> Or is a phrase something like "LE selbri KU", where "selbri" is one of > its tokens?
A selbri has internal structure, including some terminators (I believe) so it would be represented as various phrase types.
> Is "GI NAI" a phrase? It is not by itself "valid" as in a > valid text to be parsed, but there is a rule "gik = GI NAI".
I don't think NAI is really a terminator, so "GI NAI" wouldn't be represented in my formalism.
>> There are two types of tokens: start and terminator. Each token is >> paired with a number identifying the type of phrase it starts or >> terminates. > > What are the types of phrases? Can you give some examples of tokens, > some examples of phrases, and some examples of types of phrases?
The concrete syntax I've been using is as follows: "(x" is a start token of type x, ")x" is a terminator token, non-elided, and "_)x" is an elided terminator. So an example phrase would be
(1 (2 (3 (4 )4 _)3 _)2 (3 )3 )1
This phrase is invalid, because of the second 3 phrase. Since the 2 terminator is elided, the second 3 phrase would have to be grouped under the 2 phrase after the first 3 phrase. In other words, if you removed the elided terminators and reconstructed them, the 2 terminator would go after the second 3 phrase.
I think you can see how a unique number could be assigned to each selma'o that starts a terminable phrase, and the allowed nestings declared as assumptions about the mapPhPh function, to make a mapping between lojban and the formalism.
Chris Capel -- "What is it like to be a bat? What is it like to bat a bee? What is it like to be a bee being batted? What is it like to be a batted bee?" -- The Mind's I (Hofstadter, Dennet)
To unsubscribe from this list, send mail to [email protected]
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
CFG prize challenge question
Jorge Llambías <[email protected]> · 2009-02-10 12:12 UTC · Tiki post #7933 · reply to Tiki post #7912
> On Mon, Feb 9, 2009 at 17:31, Jorge Llambías <[email protected]> wrote: >> By "blowup" you mean the number of rules increases exponentially with >> the number of terminators, right? > > Well, more like with the number of allowable parent-child phrase > relationships. E.g., you can nest a sumti in a selbri, so that's one.
Do you mean things like "ME sumti MEhU" or "BRIVLA BE sumti BEhO"?
I'm still not clear what a "phrase" is here.
> You can put a selbri in a bridi, so that's two. You can put a TO-TOI > in lots of places, so that's like ten more. Etc. And I don't assert > that the blowup is exponential--I'd sooner believe it's polynomial. > But either way I'm really not to sure how to go about *proving* it.
The number of nestings allowed is already infinite with terminators. It doesn't increase when terminators can be elided.
>>> The set of valid phrases to be parsed, P, is a set of lists of tokens. >> >> First question: Do I understand correctly that a phrase is something >> like "KOhA BRODA LE BRODA KU VAU"? > > Well, I'm thinking more abstractly. I don't think KOhA has a > terminator, so I'm just assuming that kind of word is irrelevant. And > I'm representing all terminators, so I think you'd need "BRODA LE > BRODA VAU KU VAU". But that's basically it.
(Actually, the first VAU doesn't go there, VAU terminates a bridi-tail, not a selbri. A selbri doesn't have a terminator.)
>> The number of valid (and finite) such phrases with non-elidable >> terminators is countably infinite, and so is the number with elidable >> terminators. There is no blowup there. It is the number of rules, >> things like "sumti = LE selbri KU", which is finite, that probably >> blows up. > > That's the idea.
But do "LE ME KOhA MEhU KU" and "LE NU BRODA KEI KU" count as the same phrase or different phrases? They are both "sumti = LE selbri KU". I'm still not sure what you are counting as a "phrase".
>> Or is a phrase something like "LE selbri KU", where "selbri" is one of >> its tokens? > > A selbri has internal structure, including some terminators (I > believe) so it would be represented as various phrase types.
"various" or "infinite"? A selbri can have an infinite number of terminators nested inside. It doesn't have any terminator of its own.
>> Is "GI NAI" a phrase? It is not by itself "valid" as in a >> valid text to be parsed, but there is a rule "gik = GI NAI". > > I don't think NAI is really a terminator, so "GI NAI" wouldn't be > represented in my formalism.
Right, NAI is not a terminator. So a "phrase" is anything that has a terminator? Do "PA BOI" and "PA PA BOI" count as different phrases?
>>> There are two types of tokens: start and terminator. Each token is >>> paired with a number identifying the type of phrase it starts or >>> terminates. >> >> What are the types of phrases? Can you give some examples of tokens, >> some examples of phrases, and some examples of types of phrases? > > The concrete syntax I've been using is as follows: "(x" is a start > token of type x, ")x" is a terminator token, non-elided, and "_)x" is > an elided terminator. So an example phrase would be > > (1 (2 (3 (4 )4 _)3 _)2 (3 )3 )1 > > This phrase is invalid, because of the second 3 phrase. Since the 2 > terminator is elided, the second 3 phrase would have to be grouped > under the 2 phrase after the first 3 phrase. In other words, if you > removed the elided terminators and reconstructed them, the 2 > terminator would go after the second 3 phrase.
How can you tell that the second 3 phrase can be grouped under the 2 phrase? How can you tell it can't be grouped under the first 3 phrase?
> I think you can see how a unique number could be assigned to each > selma'o that starts a terminable phrase, and the allowed nestings > declared as assumptions about the mapPhPh function, to make a mapping > between lojban and the formalism.
Not all terminators are coupled with fixed "starter" selmaho, and some terminators can terminate different structures. This may or may not be relevant, I'm still not sure I see how this formalism works.
mu'o mi'e xorxes
To unsubscribe from this list, send mail to [email protected]
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
CFG prize challenge question
pdf23ds · 2009-02-10 16:47 UTC · Tiki post #7935 · reply to Tiki post #7912
> On Mon, Feb 9, 2009 at 9:42 PM, Chris Capel <[email protected]> wrote: >> On Mon, Feb 9, 2009 at 17:31, Jorge Llambías <[email protected]> wrote: >>> By "blowup" you mean the number of rules increases exponentially with >>> the number of terminators, right? >> >> Well, more like with the number of allowable parent-child phrase >> relationships. E.g., you can nest a sumti in a selbri, so that's one. > > Do you mean things like "ME sumti MEhU" or "BRIVLA BE sumti BEhO"? > > I'm still not clear what a "phrase" is here.
Well, I guess you could say a phrase is a start and end token and everything between them. So both your examples are phrases.
>> You can put a selbri in a bridi, so that's two. You can put a TO-TOI >> in lots of places, so that's like ten more. Etc. And I don't assert >> that the blowup is exponential--I'd sooner believe it's polynomial. >> But either way I'm really not to sure how to go about *proving* it. > > The number of nestings allowed is already infinite with terminators. > It doesn't increase when terminators can be elided.
Right, but I think the blowup might be a function of the number of
- unique* nestings allowed, which determines how complex the grammar
has to be. Many (most?) CFGs generate an infinite number of strings, but some are more complex than others.
> But do "LE ME KOhA MEhU KU" and "LE NU BRODA KEI KU" count as the same > phrase or different phrases? They are both "sumti = LE selbri KU". I'm > still not sure what you are counting as a "phrase".
They're different per the definition above, as long as you're assigning different tokens to ME and NU.
>> A selbri has internal structure, including some terminators (I >> believe) so it would be represented as various phrase types. > > "various" or "infinite"? A selbri can have an infinite number of > terminators nested inside. It doesn't have any terminator of its own.
An infinite number of different phrases, I guess.
>>> Is "GI NAI" a phrase? It is not by itself "valid" as in a >>> valid text to be parsed, but there is a rule "gik = GI NAI". >> >> I don't think NAI is really a terminator, so "GI NAI" wouldn't be >> represented in my formalism. > > Right, NAI is not a terminator. So a "phrase" is anything that has a > terminator? Do "PA BOI" and "PA PA BOI" count as different phrases?
Lerfu strings are an interesting case because they don't really have a start token. They just have a bunch of contents tokens, any one of which can start a lerfu phrase. But I think they can still be represented adequately with start and end tokens. So in this case, the two examples would count as the same phrase. There doesn't have to be a direct correspondence between valsi and tokens. A start token can represent the start of a structure however that start is introduced.
>> The concrete syntax I've been using is as follows: "(x" is a start >> token of type x, ")x" is a terminator token, non-elided, and "_)x" is >> an elided terminator. So an example phrase would be >> >> (1 (2 (3 (4 )4 _)3 _)2 (3 )3 )1 >> >> This phrase is invalid, because of the second 3 phrase. Since the 2 >> terminator is elided, the second 3 phrase would have to be grouped >> under the 2 phrase after the first 3 phrase. In other words, if you >> removed the elided terminators and reconstructed them, the 2 >> terminator would go after the second 3 phrase. > > How can you tell that the second 3 phrase can be grouped under the 2 > phrase? How can you tell it can't be grouped under the first 3 phrase?
Sorry. I'm assuming that 1s can be parents of 2s, 2s of 3s, 3-4, 1-3. For each grammar you have a list of those pairs defining what's allowed. I might have been too assuming to leave that implicit.
>> I think you can see how a unique number could be assigned to each >> selma'o that starts a terminable phrase, and the allowed nestings >> declared as assumptions about the mapPhPh function, to make a mapping >> between lojban and the formalism. > > Not all terminators are coupled with fixed "starter" selmaho, and some > terminators can terminate different structures. This may or may not be > relevant, I'm still not sure I see how this formalism works.
I don't think this matters to the fidelity of the formalism. Really, more than specific start or trm tokens in Lojban, the start and trm tokens here correspond to grammatical types in lojban. You'd have multiple types with the same terminator, which in the formal system don't need the same number.
Chris Capel -- "What is it like to be a bat? What is it like to bat a bee? What is it like to be a bee being batted? What is it like to be a batted bee?" -- The Mind's I (Hofstadter, Dennet)
To unsubscribe from this list, send mail to [email protected]
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
CFG prize challenge question
Jorge Llambías <[email protected]> · 2009-02-10 17:25 UTC · Tiki post #7936 · reply to Tiki post #7912
how this formalism is supposed to work. Suppose we have this small grammar with three elidable terminators VAU, KU and KEI:
sentence = [terms [CU]] selbri [terms] /VAU/
terms = [terms] sumti
sumti = KOhA | LE selbri /KU/
selbri = [selbri] tanru-unit
tanru-unit = BRIVLA | NU sentence /KEI/
How many start and terminator tokens do we need (if there is a small number, what are they, if there are too many to list, what are some examples) and what is it that blows up when moving from the non-elidable to the elidable case?
(Sorry if I'm being too dense.)
mu'o mi'e xorxes
To unsubscribe from this list, send mail to [email protected]
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
CFG prize challenge question
pdf23ds · 2009-02-11 04:36 UTC · Tiki post #7939 · reply to Tiki post #7912
> OK, let me try a different approach, because I really don't understand > how this formalism is supposed to work. Suppose we have this small > grammar with three elidable terminators VAU, KU and KEI: > > sentence = [terms [CU]] selbri [terms] /VAU/ > > terms = [terms] sumti > > sumti = KOhA | LE selbri /KU/ > > selbri = [selbri] tanru-unit > > tanru-unit = BRIVLA | NU sentence /KEI/ > > How many start and terminator tokens do we need (if there is a small > number, what are they, if there are too many to list, what are some > examples) and what is it that blows up when moving from the > non-elidable to the elidable case?
You'd need three pairs of tokens, for sentence/vau, le/ku, and nu/kei. Actually, maybe five. KOhA and BRIVLA probably need to be represented explicitly so that elided terminators before them don't eat following subphrases when they're not supposed to. Their terminators would never be elided.
So making 1=sentence, 2 = le, 3 = KOhA, 4 = nu, 5 = BRIVLA, the allowable nestings (parent--child) would be 1--2, 1--3, 2--4, 2--5, 4--1.
The blowup isn't actually represented in this part of the system--I have other parts representing CFG productions and their correspondence to phrases. The blowup is in the minimum number of productions in the CFG necessary to parse a given set of tokens and their nestings.
Chris Capel -- "What is it like to be a bat? What is it like to bat a bee? What is it like to be a bee being batted? What is it like to be a batted bee?" -- The Mind's I (Hofstadter, Dennet)
To unsubscribe from this list, send mail to [email protected]
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
CFG prize challenge question
Jorge Llambías <[email protected]> · 2009-02-11 11:54 UTC · Tiki post #7941 · reply to Tiki post #7912
> On Tue, Feb 10, 2009 at 11:23, Jorge Llambías <[email protected]> wrote: >> >> sentence = [terms [CU]] selbri [terms] /VAU/ >> >> terms = [terms] sumti >> >> sumti = KOhA | LE selbri /KU/ >> >> selbri = [selbri] tanru-unit >> >> tanru-unit = BRIVLA | NU sentence /KEI/ > > So making 1=sentence, 2 = le, 3 = KOhA, 4 = nu, 5 = BRIVLA, the > allowable nestings (parent--child) would be 1--2, 1--3, 2--4, 2--5, > 4--1.
Also: 1-4 and 1-5?
How can you tell for example that (1 (3 )3 (5 )5 (3 )3 )1 is valid but (1 (3 )3 (3 )3 )1 is not valid for this grammar? Is the set of valid phrases just given, in addition to the allowable nestings, at this point?
How is the role of CU taken into account? It's presence/absence will play a role in whether a preceding )2 can be elided or not.
mu'o mi'e xorxes
To unsubscribe from this list, send mail to [email protected]
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
CFG prize challenge question
pdf23ds · 2009-02-11 18:43 UTC · Tiki post #7942 · reply to Tiki post #7912
> On Wed, Feb 11, 2009 at 1:33 AM, Chris Capel <[email protected]> wrote: >> On Tue, Feb 10, 2009 at 11:23, Jorge Llambías <[email protected]> wrote: >>> >>> sentence = [terms [CU]] selbri [terms] /VAU/ >>> >>> terms = [terms] sumti >>> >>> sumti = KOhA | LE selbri /KU/ >>> >>> selbri = [selbri] tanru-unit >>> >>> tanru-unit = BRIVLA | NU sentence /KEI/ >> >> So making 1=sentence, 2 = le, 3 = KOhA, 4 = nu, 5 = BRIVLA, the >> allowable nestings (parent--child) would be 1--2, 1--3, 2--4, 2--5, >> 4--1. > > Also: 1-4 and 1-5?
Ah, yes. Missed those.
> How can you tell for example that (1 (3 )3 (5 )5 (3 )3 )1 is valid but > (1 (3 )3 (3 )3 )1 is not valid for this grammar? Is the set of valid > phrases just given, in addition to the allowable nestings, at this > point?
You can't. In this respect, the formalism falls short. I hope this will not be considered to invalidate it for its intended, limited purpose.
> How is the role of CU taken into account? It's presence/absence will > play a role in whether a preceding )2 can be elided or not.
I think CU is more of an elidable "starter" than a terminator. You could make bridi-tail a phrase type if you liked, to make the allowed phrases closer to lojban, but you still wouldn't get the effects of elision modeled properly. Once again, I think the formalism falls short.
If I'm able to prove anything interesting with my current formalism, I may try to generalize it some and prove or disprove those same properties.
Chris Capel -- "What is it like to be a bat? What is it like to bat a bee? What is it like to be a bee being batted? What is it like to be a batted bee?" -- The Mind's I (Hofstadter, Dennet)
To unsubscribe from this list, send mail to [email protected]
with the subject unsubscribe, or go to http://www.lojban.org/lsg2/, or if
