Mark Gritter (markgritter) wrote,
Mark Gritter
markgritter

A Chomsky Hierarchy Puzzle

http://tracery.io/ is a tool to generate text. Its input is a mostly context-free grammar, and it outputs random instances of the language defined by that grammar.

Why only mostly context-free? Tracery has two special features. The first is that the outcome of a rule expansion can be saved for later, as a new rule.

So, for example, the grammar

{ 
  "origin":"[a:#letters#]#a# #a# #a#",
  "letters":["a","a#letters#"]
}


defines "letters" in a standard way as the regular language a, aa, aaa, aaaa, ... But when we expand "origin" we take whichever string of 'a's got generated and bind it to the new rule "a". So "origin" produces the language "a a a", "aa aa aa", "aaa aaa aaa", ...

Moreover, Tracery includes modifiers that can be applied to the expansion of a rule. Most are things like "capitalize the first letter" or "add -s or -es as appropriate." But Tracery 2 (the dev version, unfortunately not the one with the live editor) includes a "replace" modifer in the standard implementation. That lets us take the previous example a step further:

{ 
  "origin":"[a:#letters#]#a##a.replace(a,b)##a.replace(a,c)#",
  "letters":["a","a#letters#"]
}


Now this language is definitely not context-free. In fact, it's the canonical example of a context-sensitive language.

Here's the puzzle: is Tracery, or Tracery-with-replace, powerful enough to implement any context-sensitive language? How could we show that? If not, what is the class of languages that it can implement?
Tags: geek, theory
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment