Generating random words
Posted: Wed May 14, 2008 1:19 pm
I took "context free" adjective literally and trying to generate random words in a grammar. For arbitrary grammar rule, e.g.
A : a B C;
it might be challenging to establish correspondence between terminal symbol positions in the derived word, on one side, and shape coordinates on the plane, on the other. However, if restricted to regular language, then the grammar can be always represented in a normal form so that each rule
B : a C;
has a terminal symbol in the first position and optional nonterminal in the second. Then, it is immediate that Y should be plotted shifted one position (whatever this may mean in the plane coordinates).
To be more concrete, here is a word in free language on alphabet {a,b}:
startshape GRAMMAR
include lower_alphabet.cfdg
rule GRAMMAR 10 {
a_lower {}
GRAMMAR { x 20 }
}
rule GRAMMAR 10 {
b_lower {}
GRAMMAR { x 20 }
}
rule GRAMMAR 1 {
EMPTY_WORD {}
}
rule EMPTY_WORD {
SQUARE { s 5 1 y -5 b 0.9 }
}
Now, I expected it to render a random word in 10 symbols, it outputs abbb_. In fact, it behaves not intuitively on the parameter ranged from 1 to 1000:
* from 1 to 4 it gives the words of increasing lengths as expected
* then up to 300 the output doesn't change
* after the 300 it generates long word which disappears
Any comments?
A : a B C;
it might be challenging to establish correspondence between terminal symbol positions in the derived word, on one side, and shape coordinates on the plane, on the other. However, if restricted to regular language, then the grammar can be always represented in a normal form so that each rule
B : a C;
has a terminal symbol in the first position and optional nonterminal in the second. Then, it is immediate that Y should be plotted shifted one position (whatever this may mean in the plane coordinates).
To be more concrete, here is a word in free language on alphabet {a,b}:
startshape GRAMMAR
include lower_alphabet.cfdg
rule GRAMMAR 10 {
a_lower {}
GRAMMAR { x 20 }
}
rule GRAMMAR 10 {
b_lower {}
GRAMMAR { x 20 }
}
rule GRAMMAR 1 {
EMPTY_WORD {}
}
rule EMPTY_WORD {
SQUARE { s 5 1 y -5 b 0.9 }
}
Now, I expected it to render a random word in 10 symbols, it outputs abbb_. In fact, it behaves not intuitively on the parameter ranged from 1 to 1000:
* from 1 to 4 it gives the words of increasing lengths as expected
* then up to 300 the output doesn't change
* after the 300 it generates long word which disappears
Any comments?