|
|
| (не показано 80 промежуточных версий 2 участников) |
| Строка 1: |
Строка 1: |
| − | = Перечисления графов = | + | {{Теорема |
| | + | |statement= Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима. |
| | + | |proof= |
| | + | Пусть <tex>A = \{ (G_1, G_2) \mid L(G_1) \cap L(G_2) = \varnothing \}</tex>. Сведем [[Примеры неразрешимых задач: проблема соответствий Поста|проблему соответствий Поста]] к <tex>\overline{A}</tex>, таким образом показав, что дополнение проблемы неразрешимо. Так как рекурсивные языки [[Замкнутость разрешимых и перечислимых языков относительно теоретико-множественных и алгебраических операций|замкнуты относительно дополнения]], то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы. |
| | | | |
| − | == Помеченные графы == | + | Для любого экземпляра ПСП <tex>(x_1, x_2, ..., x_n)</tex> и <tex>(y_1, y_2, ..., y_n)</tex> над алфавитом <tex>\Sigma</tex> можно подобрать символ <tex>\# \notin \Sigma</tex>. Для каждого экземпляра построим грамматики: |
| | + | * <tex>G_1 : S \rightarrow aSa \mid a\#a</tex> для всех <tex>a \in \Sigma</tex>. Тогда <tex>L(G_1) = \{ w\#w^R \mid w \in \Sigma^* \}</tex>, где обозначение <tex>w^R</tex> {{---}} разворот <tex>w</tex>. |
| | + | * <tex>G_2 : S \rightarrow x_iSy^R_i \mid x_i\#y^R_i</tex> для всех <tex>i = 1, 2, \dots n</tex>. Тогда <tex>L(G_2) = \{ x_{i_1} x_{i_2} \dots x_{i_m} \# (y_{i_1} y_{i_2} \dots y_{i_m})^R \mid i_1, i_2, \dots i_m \in \{ 1, 2, \dots n \}, m \geqslant 1 \}</tex>. |
| | | | |
| − | {{Определение
| + | Если данный экземпляр ПСП имеет решение, то <tex>L(G_2)</tex> содержит хотя бы одну строку вида <tex>w\#w^R</tex>, поэтому <tex>L(G_1) \cap L(G_2) \ne \varnothing</tex>, и наоборот, если он не имеет решения, то <tex>L(G_2)</tex> не содержит строк такого вида, соответственно <tex>L(G_1) \cap L(G_2) = \varnothing</tex>. |
| − | |definition =
| |
| − | '''Помеченный граф''' с <tex>n</tex> вершинами {{---}} граф, у которого каждая вершина помечена целым числом от <tex>1</tex> до <tex>n</tex>.
| |
| − | }}
| |
| | | | |
| − | Более формально определить это понятие можно так: назовем распределением <tex>f</tex> меток в графе <tex>G</tex> с <tex>n</tex> вершинами биекцию между множеством вершин графа и множеством <tex>\{1 \cdots n\}</tex>. Тогда помеченным графом называется пара <tex>(G, f)</tex>.
| + | Таким образом мы свели проблему соответствий Поста к <tex>\overline{A}</tex>, следовательно, задача о проверке на пустоту пересечения двух КС-грамматик неразрешима. |
| − | | |
| − | {{Определение
| |
| − | |definition =
| |
| − | Два помеченных графа <tex>(G_{1}, f_{1})</tex> и <tex>(G_{2}, f_{2})</tex> '''изоморфны''', если существует изоморфизм между <tex>G_{1}</tex> и <tex>G_{2}</tex>, сохраняющий распределение меток.
| |
| | }} | | }} |
| | + | Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Рассмотрим несколько примеров. |
| | | | |
| − | Все помеченные графы с тремя вершинами показаны на рисунке 1. <tex>4</tex> различных графа с <tex>3</tex> вершинами приводят к <tex>8</tex> различным помеченным графам.
| + | По двум КС-грамматикам <tex>G_1</tex> и <tex>G_2</tex> можно построить КС-грамматику для [[Замкнутость КС-языков относительно различных операций#.D0.9A.D0.BE.D0.BD.D0.BA.D0.B0.D1.82.D0.B5.D0.BD.D0.B0.D1.86.D0.B8.D1.8F|конкатенации]] задаваемых ими языков <tex>L(G_1)L(G_2)</tex>. По аналогии с этим мы можем рассматривать язык <tex>L(G_1)\#L(G_2)\#</tex>, где <tex>\#</tex> {{---}} новый символ, не встречающийся в алфавите. Заметим, что пересечение языков непусто, то есть <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex>, тогда и только тогда, когда <tex>L(G_1)\#L(G_2)\#</tex> содержит [[Алгоритм Ландау-Шмидта#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F|тандемный повтор]]. |
| | | | |
| − | {| cellpadding="2"
| + | Аналогично можно заметить, что пересечение <tex>L(G_1) \cap L(G_2) \ne \varnothing </tex> тогда и только тогда, когда <tex>L(G_1)\#L(G_2)^R</tex> содержит палиндром. |
| − | | || [[Файл:Перечисл1.jpg|thumb|left|420px|Рис. 1. Помеченные графы с тремя вершинами.]]
| |
| − | |}
| |
| | | | |
| − | Для нахождения числа помеченных графов с <tex>p</tex> вершинами нужно заметить, что каждое из <tex dpi = "165"> p\choose 2</tex> возможных ребер либо принадлежит графу, либо нет.
| + | Таким образом, мы имеем: |
| − | | + | {{Утверждение |
| − | {{Теорема | + | |statement= Пусть дана грамматика <tex>G</tex>, <tex>L(G) = L</tex>. Тогда следующие задачи неразрешимы: |
| − | |about=1
| + | # Содержит ли <tex>L</tex> тандемный повтор. |
| − | |statement= | + | # Содержит ли <tex>L</tex> палиндром. |
| − | Число помеченных графов с <tex>p</tex> вершинами равно <tex dpi = "165"> 2^{p\choose 2}</tex>.}}
| |
| − | | |
| − | Следовательно, число помеченных графов с <tex>q</tex> ребрами равно <tex dpi = "165"> {p\choose 2}\choose q</tex>.
| |
| − | | |
| − | {{Теорема
| |
| − | |author=Кэли
| |
| − | |statement=
| |
| − | Число помеченных деревьев с <tex>p</tex> вершинами равно <tex> p^{p - 2}</tex>.}}
| |
| − | | |
| − | {{Теорема
| |
| − | |about=2
| |
| − | |statement=
| |
| − | Данный граф <tex>G</tex> можно пометить <tex dpi = "160">\frac{p!}{|\Gamma(G)|}</tex> способами.
| |
| − | |proof=
| |
| − | Приведем набросок доказательства.
| |
| − | | |
| − | Пусть <tex>A</tex> {{---}} группа подстановок, действующая на множестве <tex>X</tex>. Для всякого элемента <tex>x \in X</tex> '''орбитой''' <tex>\Theta(x)</tex> элемента <tex>x</tex> называется подмножество множества <tex>X</tex>, состоящее из всех элементов <tex>y \in X</tex> таких, что <tex>\alpha \cdot x = y</tex> для некоторой подстановки <tex>\alpha</tex> из <tex>A</tex>. '''Стабилизатором''' <tex>A(x)</tex> элемента <tex>x</tex> называется подгруппа группы <tex>A</tex>, состоящая из всех подстановок из <tex>A</tex>, оставляющих элемент <tex>x</tex> неподвижным. Теорема является следствием соотношения <tex>|A| = |\Theta(x)|\cdot|A(x)|</tex> и его интерпретации в настоящем контексте.}}
| |
| − | | |
| − | {| cellpadding="2"
| |
| − | | || [[Файл:Перечисл2.jpg|thumb|left|720px|Рис. 2. Помеченные деревья с четырьмя вершинами.]]
| |
| − | |}
| |
| − | | |
| − | Рассмотрим пример. На рисунке 2 изображены все помеченные деревья с четырьмя вершинами. Всего их <tex>16</tex>. Среди них <tex>12</tex> изоморфны цепи <tex>P_{4}</tex> и <tex>4</tex> {{---}} графу <tex>K_{1, 3}</tex>. Порядок группы <tex>\Gamma(P_{4})</tex> равен <tex>2</tex>. Порядок группы <tex>K_{1, 3} = 6</tex>. Так как <tex>p = 4</tex>, то имеем <tex dpi = "160">\frac{4!}{|\Gamma(P_{4})|} = 12</tex> и <tex dpi = "160">\frac{4!}{|\Gamma(K_{1, 3})|} = 4</tex>.
| |
| − | | |
| − | == Теорема перечисления Пойа ==
| |
| − | | |
| − | Пойа показал, как получить формулу, перечисляющую орбиты в соответствии с весами и зависящую от циклической структуры подстановок данной группы.
| |
| − | | |
| − | {{Теорема
| |
| − | |statement=
| |
| − | Пусть <tex>A</tex> {{---}} группа подстановок, действующая на множестве <tex>X</tex> с орбитами <tex>\Theta_{1}, \Theta_{2} \cdots \Theta_{n}</tex> и <tex>\omega</tex> {{---}} функция, приписывающая веса каждой орбите (весовая функция). Более того, <tex>\omega</tex> определяется на <tex>X</tex> так, что <tex>\omega(x) = \omega(\Theta_{i})</tex>, если <tex>x \in \Theta_{i}</tex>. Тогда сумма весов орбит равна <tex>|A| \sum\limits_{i=1}^n \omega(\Theta_{i}) = \sum\limits_{\alpha \in A} \sum\limits_{x = \alpha x} \omega(x)</tex>.
| |
| − | |proof=
| |
| − | Уже упоминалось о том, что порядок <tex>|A|</tex> группы <tex>A</tex> равен <tex>|A(x)| \cdot |\Theta(x)|</tex> для любого <tex>x \in X</tex>, где <tex>A(x)</tex> {{---}} стабилизатор элемента <tex>x</tex>. Так как весовая функция постоянна на элементах данной орбиты, то справедливо равенство <tex>|\Theta_{i}| \omega(\Theta_{i}) = \sum\limits_{x \in \Theta_{i}}\omega(x)</tex> для каждой орбиты <tex>\Theta_{i}</tex>. Домножив второе равенство на первое и сократив, получаем <tex>|A| \omega(\Theta_{i}) = \sum\limits_{x \in \Theta_{i}}|A(x)|\omega(x)</tex>. Суммируя по всем орбитам, находим <tex>|A|\sum\limits_{i=1}^n \omega(\Theta_{i}) = \sum\limits_{i=1}^n \sum\limits_{x \in \Theta_{i}}|A(x)|\omega(x)</tex>, откуда непосредственно следует доказываемое соотношение.
| |
| | }} | | }} |
| Теорема: |
Задача о проверке на пустоту пересечения двух КС-грамматик неразрешима. |
| Доказательство: |
| [math]\triangleright[/math] |
|
Пусть [math]A = \{ (G_1, G_2) \mid L(G_1) \cap L(G_2) = \varnothing \}[/math]. Сведем проблему соответствий Поста к [math]\overline{A}[/math], таким образом показав, что дополнение проблемы неразрешимо. Так как рекурсивные языки замкнуты относительно дополнения, то из неразрешимости дополнения проблемы будет следовать неразрешимость самой проблемы.
Для любого экземпляра ПСП [math](x_1, x_2, ..., x_n)[/math] и [math](y_1, y_2, ..., y_n)[/math] над алфавитом [math]\Sigma[/math] можно подобрать символ [math]\# \notin \Sigma[/math]. Для каждого экземпляра построим грамматики:
- [math]G_1 : S \rightarrow aSa \mid a\#a[/math] для всех [math]a \in \Sigma[/math]. Тогда [math]L(G_1) = \{ w\#w^R \mid w \in \Sigma^* \}[/math], где обозначение [math]w^R[/math] — разворот [math]w[/math].
- [math]G_2 : S \rightarrow x_iSy^R_i \mid x_i\#y^R_i[/math] для всех [math]i = 1, 2, \dots n[/math]. Тогда [math]L(G_2) = \{ x_{i_1} x_{i_2} \dots x_{i_m} \# (y_{i_1} y_{i_2} \dots y_{i_m})^R \mid i_1, i_2, \dots i_m \in \{ 1, 2, \dots n \}, m \geqslant 1 \}[/math].
Если данный экземпляр ПСП имеет решение, то [math]L(G_2)[/math] содержит хотя бы одну строку вида [math]w\#w^R[/math], поэтому [math]L(G_1) \cap L(G_2) \ne \varnothing[/math], и наоборот, если он не имеет решения, то [math]L(G_2)[/math] не содержит строк такого вида, соответственно [math]L(G_1) \cap L(G_2) = \varnothing[/math].
Таким образом мы свели проблему соответствий Поста к [math]\overline{A}[/math], следовательно, задача о проверке на пустоту пересечения двух КС-грамматик неразрешима. |
| [math]\triangleleft[/math] |
Из неразрешимости вышеприведенной задачи следует неразрешимость ряда других задач. Рассмотрим несколько примеров.
По двум КС-грамматикам [math]G_1[/math] и [math]G_2[/math] можно построить КС-грамматику для конкатенации задаваемых ими языков [math]L(G_1)L(G_2)[/math]. По аналогии с этим мы можем рассматривать язык [math]L(G_1)\#L(G_2)\#[/math], где [math]\#[/math] — новый символ, не встречающийся в алфавите. Заметим, что пересечение языков непусто, то есть [math]L(G_1) \cap L(G_2) \ne \varnothing [/math], тогда и только тогда, когда [math]L(G_1)\#L(G_2)\#[/math] содержит тандемный повтор.
Аналогично можно заметить, что пересечение [math]L(G_1) \cap L(G_2) \ne \varnothing [/math] тогда и только тогда, когда [math]L(G_1)\#L(G_2)^R[/math] содержит палиндром.
Таким образом, мы имеем:
| Утверждение: |
Пусть дана грамматика [math]G[/math], [math]L(G) = L[/math]. Тогда следующие задачи неразрешимы:
- Содержит ли [math]L[/math] тандемный повтор.
- Содержит ли [math]L[/math] палиндром.
|
