¿Las referencias cruzadas son libres de contexto?

Question

Primero, un poco de historia: En XML existe la posibilidad de que una parte de un documento XML haga referencia a otra parte del documento (es decir, una referencia cruzada). A continuación se muestra un ejemplo. El elemento BookSigning hace referencia a un elemento Book:

<Library>
        <BookCatalogue>
            ...
            <Book isbn="0-440-34319-4">
                    <Title>Illusions</Title>
                    <Author>Richard Bach</Author>
            </Book>
            ...
        </BookCatalogue>

        <BookSignings>
            ...
            <BookSigning isbn\_ref="0-440-34319-4" />
            ...
        </BookSignings> 
</Library>

Eso es, isbn_ref señala isbn . El valor de isbn_ref y isbn partido.

Si no hay ninguna coincidencia isbn entonces el isbn_ref es colgando y el XML no es válido.

Quiero saber si las referencias cruzadas en XML pueden expresarse mediante una gramática libre de contexto (CFG). O bien, ¿el uso de referencias cruzadas hace que XML sea sensible al contexto?

Tratar con la sintaxis XML es demasiado complicado, así que me gustaría abstraer el problema a algo más manejable. Creo que las referencias cruzadas en XML son análogas a esto: Dejemos que x representan cualquier elemento XML y a representan un extremo de una referencia cruzada. Podríamos tener un documento XML sin referencias cruzadas, que corresponde a una secuencia de x's :

xxxxxxxxxxxxx

Supongamos que el documento XML tiene una referencia cruzada, entonces tiene un a y en algún otro lugar del documento debe haber exactamente otro a . Así que entre los x's debe haber cero a's o exactamente dos a's :

xxxxxxaxxxxxxaxxxx

Escribí una CFG para ese lenguaje:

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

Por lo tanto, si tengo una abstracción correcta de las referencias cruzadas en XML, entonces he demostrado que las referencias cruzadas en XML son libres de contexto. El problema es que no estoy convencido de que mi abstracción represente fielmente las referencias cruzadas en XML. ¿Tengo una abstracción correcta? ¿Las referencias cruzadas son libres de contexto?

Answer 1

Creo que hay un argumento bastante convincente pero informal de que las referencias cruzadas no son libres de contexto. Un lenguaje libre de contexto puede ser emparejado por un autómata push-down. Sin embargo, si tienes múltiples referencias cruzadas y los IDs se extraen de un conjunto no limitado, necesitas "recordar" todos los IDs que has visto, por lo que no puedes garantizar que el que necesitas estará en la parte superior de la pila cuando encuentres una referencia.

(Por si sirve de algo, creo que tu abstracción también se rompe ante la posibilidad de múltiples referencias a un mismo DNI, pero eso es al margen).

Answer 2

De hecho, se trata de un problema muy antiguo.

Robert W. Floyd (On the nonexistence of a phrase structure grammar for ALGOL 60 , Communications of the ACM, 1962) escribe "ALGOL 60 está definido en parte por mecanismos formales de la gramática de la estructura de la frase, en parte por restricciones declaradas informalmente. Se demuestra que ningún mecanismo formal del tipo utilizado es suficiente para definir ALGOL 60".

La estructura del propio lenguaje de programación (ALGOL, en su caso un conjunto fijo de XML) es libre de contexto, pero el requisito adicional de que las variables utilizadas coincidan con las declaradas (en su caso las referencias cruzadas deben aparecer antes) hace que el lenguaje no sea libre de contexto.

Se puede obtener una prueba formal utilizando la clásica lema de bombeo para lenguajes libres de contexto. (La variante más sofisticada de Ogden parece no ser necesaria.) Floyd utilizó el programa comenzar real x ${}^{(n)}$ ; x ${}^{(n)}$ := x ${}^{(n)}$ fin donde x ${}^{(n)}$ significa $n$ ocurrencias de la letra x. No se puede bombear dentro de los programas ALGOL60.

Esto se basa en el hecho de que las lenguas $\{ a^nba^nba^n \mid n\ge 1 \}$ no es libre de contexto. Un ejemplo similar (para un solo referencia) puede basarse en la lengua $\{ wcw \mid w\in \{a,b\}^* \}$ que tampoco es libre de contexto.