# 3-40 incomplete proceudre definition in answer video

 5 expand procedure definition presented in 3-40 answer video is not really a complete one. If you run it on tokens = [["exp","exp"]]  it will expand only one found "exp" per each returned list ['exp', 'exp'] ['exp', '+', 'exp', 'exp'] ['exp', '-', 'exp', 'exp'] ['(', 'exp', ')', 'exp'] ['num', 'exp'] ['exp', 'exp', '+', 'exp'] ['exp', 'exp', '-', 'exp'] ['exp', '(', 'exp', ')'] ['exp', 'num']  ...and as i prsume it should return ['exp', 'exp'] ['exp', '+', 'exp', 'exp', '+', 'exp'] ['exp', '+', 'exp', 'exp', '-', 'exp'] ['exp', '+', 'exp', '(', 'exp', ')'] ['exp', '+', 'exp', 'num'] ['exp', '-', 'exp', 'exp', '+', 'exp'] ['exp', '-', 'exp', 'exp', '-', 'exp'] ['exp', '-', 'exp', '(', 'exp', ')'] ['exp', '-', 'exp', 'num'] ['(', 'exp', ')', 'exp', '+', 'exp'] ['(', 'exp', ')', 'exp', '-', 'exp'] ['(', 'exp', ')', '(', 'exp', ')'] ['(', 'exp', ')', 'num'] ['num', 'exp', '+', 'exp'] ['num', 'exp', '-', 'exp'] ['num', '(', 'exp', ')'] ['num', 'num']  asked 30 Apr '12, 15:51 Tomasz Frydr... 1.1k●7 accept rate: 50%

 0 Actually, it shouldn't - that would be cheating! Why, you ask? Well, we have this depth parameter, and it says: how many edits can the resulting strings be separated away from the starting point. But to get from exp exp to num num you would need to replace not one, but two terms (non-terminals). So you're totally cheating! On a more serious note, it doesn't actually matter how many non-terminals (of the same type or different) you have on the right-hand side of a rule. Even if it says exp ten times. One edit takes only one non-terminal, and replaces it with just one rule. You don't take all the exps and replace them at the same time. It's certainly a valid production to do so, but it takes more than 1 step. answered 30 Apr '12, 16:14 Ivaylo Dankolov 1.2k●7 If i will expand only first one, then i will never touch the second "exp". [exp, exp] -> [exp, +, exp, exp] -> [exp, +, exp, +, exp, exp] -> ...  As you can see, the last exp is never touched. (30 Apr '12, 16:35) Tomasz Frydr... Well, yes, though that is in no way a problem with the approach. I'd say it's a matter of the video not being clear enough rather than an incomplete definition (see my other comment). (30 Apr '12, 16:43) Ivaylo Dankolov definition = procedure body :D (30 Apr '12, 16:58) Tomasz Frydr... Still, the procedure was ment to be used in a brute force check whether a sentence is in correct in a grammar. Solution showed in the video wont generate all possible sentence for any depth. (30 Apr '12, 17:01) Tomasz Frydr...
 0 Try increasing the depth constant. answered 30 Apr '12, 16:14 Michael F 6.6k●7●30●68 Depth is not for saying how many "exp"s from tokens are to be evaluated, but how many times do we expand the whole tokens list. But during each expand it should "touch" every each nonterminal that it finds in the tokens list. (30 Apr '12, 16:32) Tomasz Frydr... Perhaps I should have added '...and see how many of the values you believe are 'missing' appear' I'm pretty sure what it's doing is right. It starts with your ['exp', 'exp'] in utterances and it adds to utterances each possible expansion of the first 'exp', leaving the 2nd intact, and then each possible expansion of the 2nd exp, leaving the first intact. That's depth 1. If it loops again (i.e if depth is > 1 ) it will expand as above, only now, as it expands the first exp, the 2nd exp is (in many of the entries) already expanded and hence for depth 2, the values where exp and exp are both expanded to, say, exp + exp will appear. As well as where they are both expanded to num num and so on. At depth 2 there are far more values that you suggested were missing (although I'm sure all the missing ones you mention are there) To answer your specific question below to Ivaylo, ['exp', '-', 'exp', '+', 'exp', '-', 'exp'] appears in the expansion of ["exp","+","exp"] at depth 2 (02 May '12, 21:50) Michael F
 0 Depth is not for saying how many "exp"s from tokens are to be evaluated, but how many times do we expand the whole tokens list. But during each expand it should "touch" every each nonterminal that it finds in the tokens list. If i will expand only first one, then i will never touch the second "exp". [exp, exp] -> [exp, +, exp, exp] -> [exp, +, exp, +, exp, exp] -> ...  As you can see, the last exp is never touched. If we would have tokens = ["exp","+","exp"]  we would never got to ["exp","+","exp","+","exp","+","exp"] which is a valid sentence in that grammar. answered 30 Apr '12, 16:18 Tomasz Frydr... 1.1k●7 Hmm, I re-watched the video and indeed, it could be treated either way. Ah, the ambiguities of spoken language. Well, in any case all possible strings would be generated, though a replacement in formal grammars is generally defined one non-terminal at a time, and a path as the transitive closure (*, repeat) of that. I suppose you could also treat depth as the height of the syntax tree - and we've come full circle again. Anyway, your "grab everything" approach would be more efficient as the memory usage depends on the height of the tree, which might be as little as Θ(log n) where n is the parts of the final string (30 Apr '12, 16:40) Ivaylo Dankolov Never the less, the procedure was mented to generate all possibile sentences in the grammar, and it wont. (30 Apr '12, 16:42) Tomasz Frydr... Why would it not? That is how all the possible sentences in a grammar is defined: a word w is in the language of the grammar if there exists a path from the starting symbol to w, by replacing one non-terminal in a single step. The procedure in the video only expands the string one more step further, and when you apply it to all possible strings (not just words in the language) that can be generated in n steps, you get all that can be generated in n+1 steps. In fact it will generate even more strings than your proposed procedure, though of course both will catch all the words in the language (so you might say it's wasteful, and it is, but it is not incorrect). Edit: I think I should include this wikipedia link that precisely defines it. Look under the semantics of grammars - yes it's formal, but there's definitely no room for ambiguity. (30 Apr '12, 17:04) Ivaylo Dankolov How would you expand [exp,+,exp] into [exp,-,exp,+,exp,-,exp] ? (30 Apr '12, 17:22) Tomasz Frydr... There are two paths you can take : exp + exp => exp - exp + exp => exp - exp + exp - exp exp + exp => exp + exp - exp => exp - exp + exp - exp Now, these only the first steps would appear after you call expand ones. Let's say for brevity that the - was your only rule, then calling expand will yield ( [exp,-,exp,+,exp],[exp,+,exp,-,exp] ). Then, as you advance to the next level - all paths of length two, expanding the first item in the generator would yield your desired result once, expanding the second item would yield it again. Each word isn't even guaranteed to appear only once, but that's a side effect of the grammar ambiguity and not the method of choice - yours would do the same if you wanted to, say, get a long string of num+num+num+num... starting from exp. (30 Apr '12, 17:40) Ivaylo Dankolov
 0 I was also searching for the same answer, so +1 on that question, But most probably it is because, simply writing two expression does not mean anything! for example, writing : a=1; b=3; ab;  does not mean anything! answered 05 May '12, 07:49 Md. Sadaf Noor 1.2k●1●17
 0 I agree with Tomasz .. depth applies to how many times you should expand a resulting token (from an expansion). Even with depth 1. processing each token (an not its resultant) you should be able to generate all possible combinations resulting from the grammar definition. +1 answered 29 May '12, 14:17 Nishith Agga... 129●4
Question text:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

### Tags:

×1,947
×80
×43
×23

Asked: 30 Apr '12, 15:51

Seen: 311 times

Last updated: 29 May '12, 14:17