En informática teórica , un lenguaje de patrones es un lenguaje formal que puede definirse como el conjunto de todas las instancias particulares de una cadena de constantes y variables. Los lenguajes de patrones fueron introducidos por Dana Angluin en el contexto del aprendizaje automático . [1]
Definición
Dado un conjunto finito de Σ constantes símbolos y un conjunto numerable X de variable de símbolos disjunta de Σ, un patrón es un finito no vacío cadena de símbolos de Σ∪ X . La longitud de un patrón p , denotado por | p |, es solo el número de sus símbolos. El conjunto de todos los patrones que contienen exactamente n variables distintas (cada una de las cuales puede ocurrir varias veces) se denota por P n , el conjunto de todos los patrones por P * . Una sustitución es un mapeo f : P * → P * tal que [nota 1]
- f es un homomorfismo con respecto a la concatenación de cadenas (⋅), formalmente: ∀ p , q ∈ P * . f ( p ⋅ q ) = f ( p ) ⋅ f ( q );
- f no se borra, formalmente: ∀ p ∈ P * . f ( p ) ≠ ε, donde ε denota la cadena vacía ; y
- f respeta las constantes, formalmente: ∀ s ∈Σ. f ( s ) = s .
Si p = f ( q ) para algunos patrones p , q ∈ P * y alguna sustitución f , entonces se dice que p es menos general que q , escrito p ≤ q ; en ese caso, necesariamente | p | ≥ | q | sostiene. Para un patrón p , su lenguaje se define como el conjunto de todos los patrones menos generales que se construyen solo a partir de constantes, formalmente: L ( p ) = { s ∈ Σ + : s ≤ p }, donde Σ + denota el conjunto de todos cadenas finitas no vacías de símbolos de Σ.
Por ejemplo, usando las constantes Σ = {0, 1} y las variables X = { x , y , z , ...}, el patrón 0 x 10 xx 1 ∈ P 1 y xxy ∈ P 2 tiene longitud 7 y 3 , respectivamente. Una instancia del patrón anterior es 00 z 100 z 0 z 1 y 01 z 101 z 1 z 1, se obtiene mediante la sustitución que asigna x a 0 z y 1 z , respectivamente, y cada símbolo a sí mismo. Tanto 00 z 100 z 0 z 1 como 01 z 101 z 1 z 1 también son instancias de xxy . De hecho, L (0 x 10 xx 1) es un subconjunto de L ( xxy ). El lenguaje del patrón x 0 y x 1 es el conjunto de todas las cadenas de bits que denotan un número binario par e impar , respectivamente. El lenguaje de xx es el conjunto de todas las cadenas que se pueden obtener concatenando una cadena de bits consigo misma, por ejemplo, 00, 11, 0101, 1010, 11101110 ∈ L ( xx ).
Propiedades
El problema de decidir si s ∈ L ( p ) para una cadena arbitraria s ∈ Σ + y el patrón p es NP-completo (ver imagen), y también lo es el problema de decidir p ≤ q para patrones arbitrarios p , q . [2]
La clase de lenguajes de patrones no está cerrada bajo ...
- unión: por ejemplo, para Σ = {0,1} como arriba , L (01) ∪ L (10) no es un lenguaje de patrones;
- complemento: Σ + \ L (0) no es un lenguaje de patrones;
- intersección: L ( x 0 y ) ∩ L ( x 1 y ) no es un lenguaje de patrones;
- Kleene plus : L (0) + no es un lenguaje de patrones;
- homomorfismo: f ( L ( x )) = L (0) + no es un lenguaje de patrones, suponiendo que f (0) = 0 = f (1);
- homomorfismo inverso : f −1 (111) = {01, 10, 000} no es un lenguaje de patrones, asumiendo f (0) = 1 yf (1) = 11.
La clase de lenguajes de patrones está cerrada bajo ...
- concatenación: L ( p ) ⋅ L ( q ) = L ( p ⋅ q );
- inversión: L ( p ) rev = L ( p rev ). [3]
Si p , q ∈ P 1 son patrones que contienen exactamente una variable, entonces p ≤ q si y solo si L ( p ) ⊆ L ( q ); la misma equivalencia es válida para patrones de igual longitud. [4] Para patrones de diferente longitud, el ejemplo anterior p = 0 x 10 xx 1 y q = xxy muestra que L ( p ) ⊆ L ( q ) puede mantenerse sin implicar que p ≤ q . Sin embargo, cualquiera de los dos patrones de p y q , de longitudes arbitrarias, generan el mismo lenguaje si y sólo si son iguales hasta el cambio de nombre variables consistente. [5] Cada patrón p es una generalización común de todas las cadenas en su lenguaje generado L ( p ), módulo de asociatividad de (⋅).
Ubicación en la jerarquía de Chomsky
En una jerarquía refinada de Chomsky , la clase de lenguajes de patrones es una superclase y subclase adecuadas del singleton [nota 2] y los lenguajes indexados , respectivamente, pero incomparable a las clases de lengua intermedias; debido a esto último, la clase de lenguaje de patrones no se muestra explícitamente en la tabla siguiente .
La clase de lenguajes de patrones es incomparable con la clase de lenguajes finitos , con la clase de lenguajes regulares y con la clase de lenguajes libres de contexto :
- el lenguaje de patrones L ( xx ) no está libre de contexto (por lo tanto, no es regular ni finito ) debido al lema de bombeo ;
- el lenguaje finito (por lo tanto también regular y libre de contexto) {01, 10} no es un lenguaje de patrones.
Cada lenguaje singleton es trivialmente un lenguaje de patrones, generado por un patrón sin variables.
Cada lenguaje de patrones puede ser producido por una gramática indexada : por ejemplo, usando Σ = { a , b , c } y X = { x , y }, el patrón a x b y c x a y b es generado por una gramática con símbolos no terminales N = { S x , S y , S } ∪ X , símbolos terminales T = Σ, símbolos de índice F = { a x , b x , c x , a y , b y , c y }, símbolo de inicio S x y las siguientes reglas de producción:
S x [σ] | → S x [ a x σ] | | S x [ b x σ] | | S x [ c x σ] | | S y [σ] |
S y [σ] | → S y [ a y σ] | | S y [ b y σ] | | S y [ c y σ] | | S [σ] |
S [σ] | → a x [σ] b y [σ] c x [σ] a y [σ] b |
x [ a x σ] | → un | x [σ] | y [ a x σ] | → | y [σ] |
x [ b x σ] | → b | x [σ] | y [ b x σ] | → | y [σ] |
x [ c x σ] | → c | x [σ] | y [ c x σ] | → | y [σ] |
x [ a y σ] | → | x [σ] | y [ a y σ] | → un | y [σ] |
x [ b y σ] | → | x [σ] | y [ b y σ] | → b | y [σ] |
x [ c y σ] | → | x [σ] | y [ c y σ] | → c | y [σ] |
x [] | → ε | y [] | → ε |
Un ejemplo de derivación es:
S x [] ⇒ S x [ b x ] ⇒ S x [ a x b x ] ⇒ S y [ a x b x ] ⇒ S y [ c y a x b x ] ⇒ S [ c y a x b x ] ⇒ a x [ c y a x b x ] segundo y [ c y a x b x ] c x [ c y a x b x ] a y [ c y a x b x ] b ⇒ a x [ a x b x ] segundo y [ c y a x segundo x ] c x [ c y a x segundo x ] a y [ c y a x segundo x ] segundo ⇒ a a x [ segundo x ] segundo y [ c y a x segundo x ] c x [ c y a x b x ] a y [ c y a x b x ] segundo ⇒ a ab x [] b y [ c y a x b x ] c x [ c y a x b x ] a y [ c y a x b x ] b ⇒ a ab b y [ c y a x b x ] c x [ c y a x b x ] a y [ c y a x b x ] b ⇒ ... ⇒ a ab b c y [] c x [ c y a x b x ] a y [ c y a x b x ] b ⇒ a ab segundo c c x [ c y a x b x ] a y [ c y a x b x ] b ⇒ ... ⇒ a ab b c c ab x [] a y [ c y a x b x ] b ⇒ a ab b c c ab a y [ c y a x b x ] b ⇒ ... ⇒ a ab b c c ab a c y [] b ⇒ a ab b c c ab a c b
De manera similar, se puede construir una gramática índice a partir de cualquier patrón.
Patrones de aprendizaje
Dado un conjunto de muestra S de cadenas, un patrón p se denomina descriptivo de S si S ⊆ L ( p ), pero no S ⊆ L ( q ) ⊂ L ( p ) para cualquier otro patrón q .
Dado cualquier conjunto de muestra S , se puede calcular un patrón descriptivo para S mediante
- enumerando todos los patrones (hasta el cambio de nombre de la variable) no más largo que la cadena más corta en S ,
- seleccionando de ellos los patrones que generan un superconjunto de S ,
- seleccionando entre ellos los patrones de longitud máxima, y
- seleccionando entre ellos un patrón que sea mínimo con respecto a ≤. [6]
Con base en este algoritmo, la clase de lenguajes de patrones se puede identificar en el límite a partir de ejemplos positivos. [7]
Notas
- ↑ La noción de sustitución de Angluin difiere de la noción habitual de sustitución de cuerdas .
- ^ es decir, idiomas que constan de una sola cadena; corresponden a gramáticas de línea recta
Referencias
- ^ Dana Angluin (1980). "Encontrar patrones comunes a un conjunto de cadenas". Revista de Ciencias de la Computación y Sistemas . 21 : 46–62. doi : 10.1016 / 0022-0000 (80) 90041-0 .
- ↑ Teorema 3.6, p.50; Corolario 3.7, p.52
- ↑ Teorema 3.10, p.53
- ↑ Lema 3.9, p. 52; Corolario 3.4, p.50
- ↑ Teorema 3.5, p.50
- ↑ Teorema 4.1, p.53
- ^ Dana Angluin (1980). "Inferencia inductiva de lenguajes formales a partir de datos positivos" (PDF) . Información y control . 45 (2): 117-135. doi : 10.1016 / s0019-9958 (80) 90285-5 .; aquí: Ejemplo 1, p.125