Lenguaje de patrones (lenguajes formales)

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]}

• 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 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 | 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 ₁ y xxy ∈ P ₂ 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...

• unión: p. ej., 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, asumiendo f (0) = 0 = f (1);
• homomorfismo inverso : f ⁻¹ (111) = { 01, 10, 000 } no es un lenguaje de patrones, asumiendo f (0) = 1 y f (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 ₁ 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 :

• El lenguaje de patrones L ( xx ) no es libre de contexto (por lo tanto, no es ni regular ni finito ) debido al lema de bombeo ;
• El lenguaje finito (y por 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:

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

• enumerando todos los patrones (hasta el cambio de nombre de la variable) no más largos que la cadena más corta en S ,
• seleccionando de ellos los patrones que generan un superconjunto de S ,
• seleccionando de ellos los patrones de longitud máxima, y
• seleccionando de ellos un patrón que sea mínimo con respecto a ≤. ^[6]

Basándose en este algoritmo, la clase de lenguajes de patrones se puede identificar en el límite a partir de ejemplos positivos. ^[7]