[Math] Is well formed XML context-sensitive grammar

context-free-grammarformal-grammar

Solution

Copy language is noncontracting, so it's context-sensitive. Look at https://en.wikipedia.org/wiki/Noncontracting_grammar for transforming noncontracting grammar to explicitly $\alpha A \beta \rightarrow \alpha \gamma \beta$

Subj. I'm talking only about well-formed XML, i.e. all closing tags are correct.

Simplifying question: is <name></name> (where strings in opening and closing tags match) context-sensitive or unrestricted grammar?

I came out only to unrestricted grammar solution:

  1. Expand to <name> < StartReverse eman EndReverse />
  2. Reverse closing tag by pushing symbols one by one to the end

Thanks.

Best Answer

XML is a language defined by SGML, which is a restricted form of context free grammar (essentially a Dyck language with many types of parentesis). Such languages are (trivially) LL(1), thus very easy to parse.

Related Question