Page 1 of 1
monodimensional or bidimensional context-free grammar?
Posted: Mon May 01, 2006 12:19 am
by napier
Hi,
I would like to understand a theoretical foundation about the software. Are the context-free grammars implemented in the software bidimensional? Are they an extension of the 1D context-free grammars?
Posted: Mon May 01, 2006 9:46 am
by raimondious
Could you clarify the difference between 1-D and 2-D CFGs? ContextFree implements the same kind of CFG as does yacc, bison:
Ones like:
S -> A|B|aSb
A -> c|B
B -> d|S
where capitals are rules that can expand to other rules, terminal symbols (the lowercases, which are shapes in CF's case), or a combination of the two.
Posted: Mon May 01, 2006 10:54 am
by MtnViewJohn
I think that Chris can answer this question best, but here goes...
Context Free interprets a CFDG grammar to produce a 'sentence'. The sentence is an ordered list of simple shapes (squares, circles, and triangles). Each shape has a 2-D affine transform associated with it that falls out of the grammar along with the shape. This sentence is then translated into a 2-D image, but the sentence itself is a 1-D string of shape symbols. If we created a 3-D version of Context Free then the sentence would be translated into a 3-D output but it would still be 1-D.
Posted: Mon May 01, 2006 12:58 pm
by napier
Ok, now I've understood, it's the 1D case.
Raimondious, in the 2D case CFGs produce "pictures" instead of words/strings. If you want to know something more about you could search for "bidimensional grammar" on Google.
Bye bye!