analytics

Saturday, March 8, 2014

Graphst as a Left Recursive Context Free Grammar

Considering a graph such as:
I noticed that you can write the problem using rewriting rules (for this graph for example):

And so on where every letter can be replaced by a vertex connecting to it and itself, left recursively. 
So a Hamilton circuit for this graph could be generated following the rules like so:
b -> aB
aB
a -> dA
dAB
d -> gD
gDAB
g -> fG
fGDAB
f -> eF
eFGDAB
e -> cE
cEFGDAB
c -> bC
bCEFGDAB

Writing graph problems as Context Free Grammars and in this case left recursive ones gives immediately many useful theorems. See: http://en.wikipedia.org/wiki/Context-free_grammar

For example many problems about Context Free Grammars are undecidable in the general case.

No comments:

Post a Comment