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]
Dado un conjunto finito Σ de símbolos constantes y un conjunto numerable X de símbolos variables disjuntos de Σ, un patrón es una cadena finita no vacía de símbolos de Σ∪ X . La longitud de un patrón p , denotada por | p |, es simplemente 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 aparecer varias veces) se denota por P n , el conjunto de todos los patrones por P * . Una sustitución es una aplicación f : P * → P * tal que [nota 1]
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 | se cumple. 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 todas las cadenas finitas no vacías de símbolos a partir de Σ.
Por ejemplo, utilizando 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 primer patrón es 00 z 100 z 0 z 1 y 01 z 101 z 1 z 1, se obtiene por la sustitución que asigna x a 0 z y a 1 z , respectivamente, y cada otro 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 ).
El problema de decidir si s ∈ L ( p ) para una cadena arbitraria s ∈ Σ + y patrón p es NP-completo (ver imagen), y por lo tanto 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...
La clase de lenguajes de patrones está cerrada bajo...
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 se cumple 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 cumplirse sin implicar p ≤ q . Sin embargo, dos patrones cualesquiera p y q , de longitudes arbitrarias, generan el mismo lenguaje si y solo si son iguales hasta un cambio de nombre de variable consistente. [5] Cada patrón p es una generalización común de todas las cadenas en su lenguaje generado L ( p ), módulo asociatividad de (⋅).
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 incomparables con las clases de lenguaje 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 :
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:
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 [ cy a x b x ] ⇒ S [ cy a x b x ] ⇒ a x [ cy a x b x ] b y [ cy a x b x ] c x [ cy a x b x ] a y [ cy a x b x ] b ⇒ a x [ a x b x ] b y [ cy a x b x ] c x [ cy a x b x ] a y [ cy a x b x ] b ⇒ a a x [ b x ] b y [ cy a x b x ] c x [ cy a x b x ] a y [ cy a x b x ] b ⇒ a ab x [ ] b y [ cy a x b x ] c x [ cy 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 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 de índice a partir de cualquier patrón.
Dado un conjunto de muestra S de cadenas, un patrón p se llama descriptivo de S si S ⊆ L ( p ), pero no S ⊆ L ( q ) ⊂ L ( p ) para cualquier otro patrón q .
Dado cualquier conjunto de muestras S , se puede calcular un patrón descriptivo para S mediante
Basándose en este algoritmo, la clase de lenguajes de patrones se puede identificar en el límite a partir de ejemplos positivos. [7]