Mark Gritter (markgritter) wrote,
Mark Gritter

A Chomsky Hierarchy Puzzle 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#",

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:


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

  • Predictions for 2018

    Tintri asked me to put together some technology predictions for 2018. You can access the "on-demand webinar" here:…

  • Back from Tintri sales kickoff

    Tintri has historically held its sales kickoff in the Bay Area to be close to headquaters. This year we went to Las Vegas instead, at the Hard Rock…

  • Retiring another interview question

    I've been talking to people who have built cloud services that communicate with on-premises equipment (like storage arrays or routers.) One of my…

  • Post a new comment


    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