Язык шаблонов (формальные языки)

В теоретической информатике язык шаблонов — это формальный язык , который можно определить как набор всех конкретных экземпляров строки констант и переменных. Языки шаблонов были представлены Даной Англуин в контексте машинного обучения . ^[1]

Определение

Учитывая конечное множество Σ постоянных символов и счетное множество X переменных символов , не пересекающихся с Σ, шаблон представляет собой конечную непустую строку символов из Σ∪ X .Длина шаблона p , обозначаемая | p |, — это просто количество его символов.Набор всех шаблонов, содержащих ровно n различных переменных (каждая из которых может встречаться несколько раз), обозначается P _n , набор всех шаблонов вообще - P _* .Подстановкой называется такое отображение f : P _* → P _* , что ^{[примечание 1]}

f — гомоморфизм относительно конкатенации строк (⋅), формально: ∀ p , q ∈ P _* . ж ( п ⋅ q ) знак равно ж ( п )⋅ ж ( q );
f не стирает, формально: ∀ p ∈ P _* . f ( p ) ≠ ε, где ε обозначает пустую строку ; и
f соблюдает константы, формально: ∀ s ∈Σ. ж ( s ) знак равно s .

Если p = f ( q ) для некоторых шаблонов p , q ∈ P _* и некоторой замены f , то p называется менее общим, чем q , и пишется p ≤ q ;в таком случае обязательно | р | ≥ | д | держит.Для шаблона p его язык определяется как набор всех менее общих шаблонов, которые построены только из констант, формально: L ( p ) = { s ∈ Σ ⁺ : s ≤ p }, где Σ ⁺ обозначает множество всех конечных непустых строк символов из Σ.

Например, используя константы Σ = { 0, 1 } и переменные X = { x , y , z , ... }, шаблон 0 x 10 xx 1 ∈ P ₁ и xxy ∈ P ₂ имеет длину 7 и 3. , соответственно.Примером первого шаблона является 00 z 100 z 0 z 1 и 01 z 101 z 1 z 1. Он получается путем замены, которая отображает x в 0 z и в 1 z соответственно, а каждый другой символ сам в себя. Оба 00 z 100 z 0 z 1 и 01 z 101 z 1 z 1 также являются экземплярами xxy . Фактически, L (0 x 10 xx 1) является подмножеством L ( xxy ). Язык шаблона x 0 и x 1 представляет собой набор всех битовых строк, которые обозначают четное и нечетное двоичное число соответственно. Язык xx — это набор всех строк, которые можно получить путем объединения битовой строки с самой собой, например 00, 11, 0101, 1010, 11101110 ∈ L ( xx ).

Характеристики

Проблема определения того, является ли s ∈ L ( p ) для произвольной строки s ∈ Σ ⁺ и шаблон p является NP-полным (см. рисунок),и, следовательно, возникает проблема определения p ≤ q для произвольных шаблонов p , q . ^[2]

Класс языков шаблонов не закрывается под...

объединение: например, для Σ = {0,1}, как указано выше , L (01) ∪ L (10) не является языком шаблонов;
дополнение: Σ ⁺ \ L (0) не является языком шаблонов;
пересечение: L ( x 0 y ) ∩ L ( x 1 y ) не является языком шаблонов;
Клини плюс : L (0) ⁺ не является языком шаблонов;
гомоморфизм: f ( L ( x )) = L (0) ⁺ не является языком шаблонов, если предположить, что f (0) = 0 = f (1);
обратный гомоморфизм : f ⁻¹(111) = {01, 10, 000} не является языком шаблонов, если предположить, что f (0) = 1 и f (1) = 11.

Класс языков шаблонов закрыт под...

конкатенация: L ( п )⋅ L ( q ) знак равно L ( п ⋅ q );
разворот: L ( п ) ^оборот = L ( п ^оборот). ^[3]

Если p , q ∈ P1 _L — шаблоны, содержащие ровно одну переменную, то p ≤ q тогда и только тогда, когда ( p ) ⊆ L ( q );та же эквивалентность справедлива для шаблонов одинаковой длины. ^[4]Для шаблонов разной длины приведенный выше пример p = 0 x 10 xx 1 и q = xxy показывает, что L ( p ) ⊆ L ( q ) может выполняться, не подразумевая p ≤ q .Однако любые два шаблона p и q произвольной длины генерируют один и тот же язык тогда и только тогда, когда они равны с точностью до последовательного переименования переменных. ^[5]Каждый шаблон p является общим обобщением всех строк в сгенерированном им языке L ( p ) по модулю ассоциативности (⋅).

Место в иерархии Хомского

В уточненной иерархии Хомского класс языков шаблонов является собственным суперклассом и подклассом синглтона. ^{[примечание 2]} и индексированные языки соответственно, но несравнимы с промежуточными языковыми классами; из-за последнего класс языка шаблонов явно не показан в таблице ниже .

Класс шаблонных языков несравним с классом конечных языков , с классом регулярных языков и с классом контекстно-свободных языков :

язык шаблонов L ( xx ) не является контекстно-свободным (следовательно, не является ни регулярным , ни конечным ) из-за леммы о накачке ;
конечный (следовательно, также регулярный и бесконтекстный) язык { 01, 10 } не является языком шаблонов.

Каждый одноэлементный язык, по сути, является языком шаблонов, созданным по шаблону без переменных.

Каждый язык шаблонов может быть создан с помощью индексированной грамматики :Например, используя Σ = { a , b , c } и X = { x , y },шаблон a x b y c x a y b генерируется грамматикой с нетерминальными символами N = { S _x , S _y , S } ∪ X , терминальными символами T = Σ, индексными символами F = { a _x , b _x , c _x , a _y , by _, x c _y , начальный символ S _} и следующие правила производства:

S _х [σ]	→ S _x [ a _x σ]	\| S _х [ б _х σ]	\| S _x [ c _x σ]	\| S _y [σ]
S _y [σ]	→ S _y [ a _y σ]	\| s _y [ by _] σ	\| s _y [ c _y σ]	\| SS ]
SS ]	→ a x [σ] b y [σ] c x [σ] a y [σ] b

х [ а _х σ]	→ а	х [с]	у [ а _х σ]	→	й [с]
х [ б _х с]	→ б	х [с]	у [ б _х с]	→	й [с]
х [ с _х с]	→ с	х [с]	у [ с _х с]	→	й [с]
х [ а _у σ]	→	х [с]	y [ а _y σ]	→ а	й [с]
х [ у _σ ]	→	х [с]	y [ by _] σ	→ б	й [с]
х [ с _у σ]	→	х [с]	y [ c _y σ]	→ с	й [с]
х []	→ е		и []	→ е

Пример вывода:

С _х [] ⇒ S _х [ б х ⇒ S _x [ а _x b x ⇒ S _y [ а _х б х ⇒ S _y [ c _y a _x b x ⇒ S [ c _y a _x b x ⇒ a x [ c _y a _x b _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 x [ a _x b _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 a x [ b _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 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 ⇒ … ⇒ а 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 x [ c _y a _x b _x ] a y [ c _y a _x b _x ] b ⇒ … ⇒ а ab b c c ab x [] a y [ c _y a _x b _x ] b ⇒ a ab b c ab a y [ c _y a _x b _x ] b ⇒ … ⇒ а ab b c c ab a c y [] b ⇒ а аб б в с б а с б

Аналогичным образом индексная грамматика может быть построена на основе любого шаблона.

Шаблоны обучения

Учитывая выборочный набор строк S , шаблон p называется описательным для S, если S ⊆ L ( p ), но не S ⊆ L ( q ) ⊂ L ( p ) для любого другого шаблона q .

Учитывая любой набор выборок S , описательный образец для S можно вычислить с помощью

перечисление всех шаблонов (вплоть до переименования переменных) не длиннее самой короткой строки в S ,
выбирая из них шаблоны, которые порождают надмножество S ,
выбирая из них шаблоны максимальной длины, и
выбрав из них образец, минимальный по ≤. ^[6]

На основе этого алгоритма класс языков шаблонов можно в пределе выделить из положительных примеров. ^[7]

Примечания

^ Понятие замены Англуина отличается от обычного понятия замены строки .
^ т.е. языки, состоящие из одной строки; они соответствуют прямолинейным грамматикам

Ссылки

^ Дана Англуин (1980). «Нахождение закономерностей, общих для набора строк» . Журнал компьютерных и системных наук . 21 : 46–62. дои : 10.1016/0022-0000(80)90041-0 .
^ Теорема 3.6, стр.50; Следствие 3.7, с.52
^ Теорема 3.10, стр.53
^ Лемма 3.9, стр.52; Следствие 3.4, с.50
^ Теорема 3.5, стр.50
^ Теорема 4.1, стр.53
^ Дана Англуин (1980). «Индуктивный вывод формальных языков на основе положительных данных» (PDF) . Информация и контроль . 45 (2): 117–135. дои : 10.1016/s0019-9958(80)90285-5 . ; здесь: Пример 1, стр.125

[2] Понятие замены Англуина отличается от обычного понятия замены строки .

[7] т.е. языки, состоящие из одной строки; они соответствуют прямолинейным грамматикам

[1] Дана Англуин (1980). «Нахождение закономерностей, общих для набора строк» . Журнал компьютерных и системных наук . 21 : 46–62. дои : 10.1016/0022-0000(80)90041-0 .

[3] Теорема 3.6, стр.50; Следствие 3.7, с.52

[4] Теорема 3.10, стр.53

[5] Лемма 3.9, стр.52; Следствие 3.4, с.50

[6] Теорема 3.5, стр.50

[8] Теорема 4.1, стр.53

[9] Дана Англуин (1980). «Индуктивный вывод формальных языков на основе положительных данных» (PDF) . Информация и контроль . 45 (2): 117–135. дои : 10.1016/s0019-9958(80)90285-5 . ; здесь: Пример 1, стр.125

[1]

[примечание 1]

[2]

[3]

[4]

[5]

[примечание 2]

[6]

[7]