El anlisis de la ambigedad de las gramticas libres de contextoSe ha sabido desde 1962 que el problema de la ambigedad de las gramticas libres de contexto es indecidible. La ambigedad en las gramticas libres de contexto es un problema recurrente en el lenguaje diseo y la generacin de analizador, aplicaciones, as asin donde gramticas son modelos de uso das de las estructuras fsicas del mundo real.Se observa que existe una caracterizacin lingstica sencilla de la ambigedad gramtica problema, y nos muestran cmo explotar esta presentando un marco de anlisis de la ambigedad basado en aproximaciones de lenguaje conservadores. Como ejemplo concreto, se propone un la base tcnica sobre aproximaciones regulares locales y gramtica unfoldings.We evaluar la anlisis utilizando las gramticas que se producen en el anlisis de ARN en la bioinformtica, y demostrar que es suficientemente precisa y eficiente para ser til.Introduccion.Al utilizar las gramticas libres de contexto para describir lenguajes formales, uno tiene que ser consciente del potencial de la ambigedad en el gramticas, es decir, la situacin en la que una cadena puede ser analizada en mltiples formas, dando lugar a diferentes rboles de anlisis sintctico. Proponemos una tcnica para detectar ambigedades en una gramtica dada. A medida que el problema est en indecidible en general, que se muestra por Cantor [6], Floyd [14], y Chomsky y Schtzenberger [8], que recurren a la aproximacin conservadora. Esto significa que nuestro anlisis para algunas gramticas es capaz de garantizar que no son ambiguas, mientras que para otros no puede dar cierta respuestas.En la bioinformtica, las gramticas libres de contexto en diversas formas tienen aplicaciones importantes, por ejemplo en la secuencia comparacin, motivo de bsqueda, y la estructura secundaria del ARN anlisis [12,18]. Recientemente, la ambigedad ha ganado la atencin en este campo, asseveral important algorithms (tales como el algoritmo de Viterbi en CFGs estocsticos) han demostrado para entregar incorrecta resultados en la presencia de ambigedad [16,11]. El problema de la ambigedad surge en el anlisis biosecuencia de la necesidad de comprobar una propiedad esttica de los algoritmos de programacin dinmicos empleados - la cuestin de si o no un elemento de la espacio de bsqueda se puede evaluar ms de una vez. Si es as, los sistemas de puntuacin probabilsticos producen resultados incorrectos, y enumeracin de soluciones casi ptimas ahoga en la redundancia. Puede parecer sorprendente que el anlisis esttico de esta propiedad programa puede ser abordado como una cuestin de la ambigedad de idioma en el nivel del lenguaje formal. Vamos a explicar esta situacin en algunos detalle en la Seccin 8.Antes de empezar la presentacin de nuestro mtodo, declaramos dos requisitos en un prctico comprobador de ambigedad que se derivan de la biosecuencia dominio anlisis y debe tenerse en cuenta en lo que sigue: En primer lugar, las gramticas que deben controlarse son en realidad abstracciones de los conceptos de programacin ms ricos. Pueden parecer extrao desde un punto de diseo de lenguajes de vista formal- Por ejemplo, pueden contener '' los smbolos no terminales 'redundantes' que generan el mismo idioma. Sin embargo, diferenteno terminales diferentes estructuras fsicas modelo con diferentes semntica que son esenciales para la posterior algortmica processing.Hence, la gramtica debe ser revisado como es y no puede ser simplificado mediante, por ejemplo, en el terminal de coalescencia suchn smbolos. Por supuesto, es posible (y lo har) aplicar transformaciones ambigedad de preservacin de la gramtica. En segundo lugar, el dominio expertos suelen ser los bilogos moleculares con poca experiencia en programacin y ninguna formacin en la teora del lenguaje formal.Por lo tanto, cuando se descubre la ambigedad, se debe informar de una manera que sea significativa para esta categora de usuarios. Adems de las aplicaciones al anlisis biosecuencia, nuestra motivacin detrs de la obra que presentamos aqu ha estado analizando reversibilidad de transformaciones entre datos XML y no XML, que se puede reducir a la ambigedad gramtica problema [4] .Que trabajo implica escner menor anlisis, es decir, donde las descripciones lxicas no se separan de las gramticas.2. Una caracterizacin de ambigedad gramticaDefinicin 1 (gramtica libre de contexto y ambigedad).Definicin 2 (Vertical y Horizontal ambigedad)Ejemplo 4 (Vertical ambigedad).Ejemplo 5 (Horizontal ambigedad)3. Un marco para la aproximacin conservadoraDefinicin 6 (Gramtica aproximacin).Definicin 7 (aproximado Vertical y Horizontal ambigedad).4. aproximacin RegularDefinicin 11 (Mohri-Nederhof Estrategia de Aproximacin).Ejemplo 12 (palndromos)Ejemplo 13 (Expresiones ambiguas).5. Mejora de la precisin con la gramtica despliegueExample 14 (Unambiguous Expressions)Definicin 15 (Gramtica Balanced 1)Definicin 16 (Gramtica Balanced Desplegado).6. Otras estrategias de aproximacinEjemplo 19 (cadena vaca).Ejemplo 20 (mayo Must)10. ConclusinHemos presentado una tcnica, ACLA (Ambigedad Comprobacin con Idioma Aproximaciones), para analizar de forma esttica la ambigedad de las gramticas libres de contexto. Sobre la base de una caracterizacin lingstica, la tcnica permite el uso de la gramtica transformaciones, en particular aproximacin regular y despliegue, sin sacrificar la solidez. Adems, el anlisis a menudo es capaz de identificar las fuentes de ambigedad a travs de ejemplos concretos que se generan automticamente. El anlisis puede se utilizar cuando LR (k) y tcnicas relacionadas son inadecuados, por ejemplo en el anlisis biosecuencia, ya que nuestros ejemplos muestran.Nuestros experimentos indican que la precisin, la velocidad y la calidad de los informes de ambigedad son suficientes para ser prcticamente til.