Is there a fast algorithm to determine the godel number of a term of a context free language?

admin

Administrator
Staff member
Suppose we have a simple grammar specification. There is a way to enumerate terms of that grammar that guarantees that any finite term will have a finite position, <a href="http://lukepalmer.wordpress.com/2008/05/02/enumerating-a-context-free-language/">by iterating it diagonally</a>. For example, for the following grammar:

Code:
S      ::= add
add    ::= mul | add + mul
mul    ::= term | mul * term
term   ::= number | ( S )
number ::= digit | digit number
digit  ::= 0 | 1 | ... | 9

You can enumerate terms like that:

Code:
0
1
0+0
0*0
0+1
(0)
1+0
0*1
0+0*0
00
... etc

My question is: is there a way to do the opposite? That is, to take a valid term of that grammar, say,
Code:
0+0*0
, and find its position on such enumeration - in that case, 9?