I am trying to gain intuition on formal forests, also called tree languages, i.e., sets of trees. There are regular tree languages, and there are context free tree languages. They both come in a deterministic and non-deterministic variants. The definitions are clear, but I am in search of examples that are less technical and more intuitive. Consider data structures:

Is the language of all AVL trees context free? Replace AVL by leftist, red-black, some other useful data structure, e.g., binomial heap with appropriate adjustment for unbounded rank) Replace "context free tree language" by some other class of tree languages.

  • 1
    $\begingroup$ Your question probably won't be considered a research-level question in TCS, so may be better posted at cs.stackexchange.com. $\endgroup$
    – Neal Young
    Apr 10 at 21:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.