search

kalexmills / stochrammar

Stochastic grammar library implemented in Java.
GNU Affero General Public License v3.0
0 stars 0 forks source link

Theory: Characterize the class of languages generated by TreeRunner #6

Open kalexmills opened 6 years ago

kalexmills commented 6 years ago

Understand the computational power of TreeRunner by characterizing the class of languages which a deterministic variant of the class can produce. Do not raise a PR for this issue. Please post results as responses to this issue, or a link to a blog post or other write-up.

I would be surprised if it were not context-free.

kalexmills commented 6 years ago

Actually, I believe it will be trivial to use TreeRunner to simulate any context-free languages (you can convince yourself of that once I have finished writing it and put it on this repo).

The question now is whether all TreeRunner instances can be simulated by an equivalent Context-free grammar.