¿Qué buenas notaciones existen para los lenguajes deterministas libres de contexto y visiblemente pushdown?

Los lenguajes deterministas sin contexto (DCFL) y los lenguajes visiblemente pushdown (VPL) son ambos conjuntos de lenguajes formales entre lenguajes sin contexto (CFL) e idiomas regulares (REG). ¿Existe una notación legible que se pueda expresar en ASCII simple como Backus-Naur-Form para CFL y expresiones regulares para REG?

$q,z,a\to q',\gamma$$q,q'$$Q$$z$$\gamma$$a$un símbolo de entrada o la cadena vacía. La notación en sí misma no impone el determinismo, pero se verifica fácilmente. Usando un tipo de notación de gramática libre de contexto (como BNF), se encontrará con problemas, ya que los DCFL son una subclase adecuada de CFL y, como lo señala DaniCL, no puede decidir en general dado un CFG si su lenguaje es determinista.

$A\to a\alpha b$$A$$a$$b$$\alpha$

$a$$b$

Para encontrar una representación canónica, considere lo siguiente: la clase de DCFL es equivalente a la clase de lenguajes generados por las gramáticas LR (k), que nuevamente es equivalente a LR (1). Esto significa que puede encontrar una gramática LR (1) para cada DCFL. Por supuesto, una gramática LR (1) sigue siendo una gramática libre de contexto, pero con una propiedad especial: a partir de las gramáticas LR (1), podemos construir fácilmente tablas de análisis para guiar un analizador determinista (con anticipación de 1 símbolo, por lo tanto, LR (1)). Estas tablas de análisis serían otra representación, aunque algo menos legible.

Por cierto, tenga en cuenta que es indecidible si un lenguaje libre de contexto dado es determinista (Teorema de Greibach).

Debo admitir que nunca he oído hablar de VPL.