Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

First, a little background: In XML there is the ability for one part of an XML document to reference another part of the document (i.e., a cross-reference). Below is an example. The BookSigning element references a Book element:

            <Book isbn="0-440-34319-4">
                    <Author>Richard Bach</Author>

            <BookSigning isbn_ref="0-440-34319-4" />

That is, isbn_ref points to isbn. The value of isbn_ref and isbn match.

If there is no matching isbn value then the isbn_ref is dangling and the XML is invalid.

I want to know if cross-references in XML can be expressed using a Context-Free Grammar (CFG)? Or, does the use of cross-references make XML Context-Sensitive?

Dealing with the XML syntax is much too complicated, so I would like to abstract the problem to something more manageable. I believe that cross-referencing in XML is analogous to this: Let x represent any XML element and a represent one end of a cross-reference. We could have an XML document without any cross-references, which corresponds to a sequence of x's:


Suppose that the XML document has a cross-reference, then it has an a and somewhere else in the document there must be exactly one other a. So amongst the x's there must be zero a's or exactly two a's:


I wrote a CFG for that language:

S -> X | A
X -> xX | empty
A -> XaB | BaX
B -> XaX

So, if I have a correct abstraction of cross-referencing in XML, then I have proven that cross-references in XML are context-free. The problem is that I am not convinced that my abstraction faithfully represents cross-referencing in XML. Do I have a correct abstraction? Are cross-references context-free?

share|cite|improve this question
If something is to be referred to, must it have a unique value (i.e., in your example, if you had more than one book with the same ISBN, would that be invalid)? If so, proving that the language isn't context-free looks like a pretty straightforward application of Ogden's lemma. – Micah Jul 13 '13 at 19:07
Thanks Micah. Yes, you are correct: multiple books with the same ISBN is invalid. I will look into Ogden's lemma. – Roger Costello Jul 13 '13 at 19:55
up vote 1 down vote accepted

I think there's a pretty convincing but informal argument that cross-references are not context-free. A context-free language can be matched by a push-down automaton. However, if you have multiple cross-references and the IDs are drawn from an unbounded set, you need to "remember" all of the IDs you've seen, so you can't guarantee that the one you need will be at the top of the stack when you encounter a reference.

(For what it's worth, I think your abstraction also breaks down on the possibility of multiple references to the same ID, but that's by the by).

share|cite|improve this answer

This is in fact similar to a very old problem.

Robert W. Floyd (On the nonexistence of a phrase structure grammar for ALGOL 60 , Communications of the ACM, 1962) writes "ALGOL 60 is defined partly by formal mechanisms of phrase structure grammar, partly by informally stated restrictions. It is shown that no formal mechanisms of the type used are sufficient to define ALGOL 60."

The structure of the programming language itself (ALGOL, in your case a fixed set of XML) is context-free, but the additional requirement that used variables match the ones declared (in your case cross-references should appear earlier) makes the language non-context-free.

A formal proof can be obtained using the classical pumping lemma for context-free languages. (The more sophisticated variant of Ogden seems not necessary.) Floyd used the program begin real x${}^{(n)}$; x${}^{(n)}$ := x${}^{(n)}$ end where x${}^{(n)}$ stands for $n$ occurrences of the letter x. It cannot be pumped within the ALGOL60 programs.

This is based on the fact that the languages $\{ a^nba^nba^n \mid n\ge 1 \}$ is not context-free. A similar example (for a single reference) can be based on the language $\{ wcw \mid w\in \{a,b\}^* \}$, which also is not context-free.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.