Нормальная форма Куроды — различия между версиями
Строка 32: | Строка 32: | ||
Пусть <tex>N' = N \cup \{a' | a \in T\}</tex>. | Пусть <tex>N' = N \cup \{a' | a \in T\}</tex>. | ||
− | Пусть <tex>\alpha = x_1x_2...x_n</tex> {{---}} часть правила, тогда <tex>\alpha' = y_1y_2...y_n</tex>, где <tex>y_i = \{x_i</tex>, если <tex>x_i \in N</tex>; <tex>x_i'</tex>, если <tex>x_i \in T\}</tex> для <tex>1 | + | Пусть <tex>\alpha = x_1x_2...x_n</tex> {{---}} часть правила, тогда <tex>\alpha' = y_1y_2...y_n</tex>, где <tex>y_i = \{x_i</tex>, если <tex>x_i \in N</tex>; <tex>x_i'</tex>, если <tex>x_i \in T\}</tex> для <tex>1 \leqslant i \leqslant n</tex>. |
Построим грамматику <tex>G' = (N', T, P', S)</tex>, где <tex>P' = \{\alpha' \rightarrow \beta' : \alpha \rightarrow \beta \in P\} \cup \{a' \rightarrow a: a \in T\}</tex>. | Построим грамматику <tex>G' = (N', T, P', S)</tex>, где <tex>P' = \{\alpha' \rightarrow \beta' : \alpha \rightarrow \beta \in P\} \cup \{a' \rightarrow a: a \in T\}</tex>. | ||
Строка 42: | Строка 42: | ||
Согласно конструкции <tex>P'</tex>, в <tex>G'</tex> существует вывод <tex>S = w_0' => w_1' => w_2' => ... => w_n' = v_0 => v_1 => v_2 => ... => v_m = w</tex>. | Согласно конструкции <tex>P'</tex>, в <tex>G'</tex> существует вывод <tex>S = w_0' => w_1' => w_2' => ... => w_n' = v_0 => v_1 => v_2 => ... => v_m = w</tex>. | ||
− | Для <tex>0 | + | Для <tex>0 \leqslant i \leqslant n - 1</tex> в переходах <tex>w_i' => w_{i + 1}'</tex> используем правило <tex>\alpha' \rightarrow \beta'</tex>, так как правило <tex>\alpha \rightarrow \beta</tex> было использовано при выводе <tex>w_i => w_{i + 1}</tex>. |
− | Для <tex>0 | + | Для <tex>0 \leqslant j \leqslant m - 1</tex> в переходах <tex>v_j => v_{j + 1}</tex> используем правила вида <tex>a' \rightarrow a</tex>. |
Заменяем разрешенные в <tex>w'</tex> символы на новые и получаем, что <tex>w \in L(G')</tex>. | Заменяем разрешенные в <tex>w'</tex> символы на новые и получаем, что <tex>w \in L(G')</tex>. | ||
Строка 53: | Строка 53: | ||
Из построения: после применения правила вида <tex>a' \rightarrow a</tex> полученное <tex>a</tex> не может быть использовано при применении правил из <tex>P'</tex>. | Из построения: после применения правила вида <tex>a' \rightarrow a</tex> полученное <tex>a</tex> не может быть использовано при применении правил из <tex>P'</tex>. | ||
− | Изменение порядка вывода не меняет язык, то есть в <tex>G'</tex> существует вывод: <tex>S = x_0' => x_1' => ... => x_r' => x' => y_1 => y_2 => ... => y_s = x</tex>, где для <tex>0 | + | Изменение порядка вывода не меняет язык, то есть в <tex>G'</tex> существует вывод: <tex>S = x_0' => x_1' => ... => x_r' => x' => y_1 => y_2 => ... => y_s = x</tex>, где для <tex>0 \leqslant i \leqslant r - 1 x_{i + 1}' \in (N')^*</tex> и в переходе <tex>x_i' \rightarrow x_{i + 1}'</tex> было использовано правило вывода <tex>\alpha' \rightarrow \beta'</tex> и для <tex>1 \leqslant j \leqslant s</tex> было использовано правило <tex>a' \rightarrow a</tex>, чтобы получить <tex>y_j \rightarrow y_{j + 1}</tex>. |
Получаем вывод в <tex>G</tex>: <tex>S = x_0 => x_1 => ... => x_n = x</tex>. | Получаем вывод в <tex>G</tex>: <tex>S = x_0 => x_1 => ... => x_n = x</tex>. | ||
Строка 66: | Строка 66: | ||
|about=об удалении длинных правил | |about=об удалении длинных правил | ||
|statement= Для любой грамматики <tex>G = (N, T, P, S)</tex> может быть построена грамматика <tex>G' = (N', T, P', S)</tex> такая, что: | |statement= Для любой грамматики <tex>G = (N, T, P, S)</tex> может быть построена грамматика <tex>G' = (N', T, P', S)</tex> такая, что: | ||
− | * любое правило из <tex>P'</tex> имеет вид: <tex>\alpha \rightarrow \beta</tex>, где <tex>\alpha \in (N')^+</tex> и <tex>\beta \in (N')^+</tex> и <tex>|\alpha| | + | * любое правило из <tex>P'</tex> имеет вид: <tex>\alpha \rightarrow \beta</tex>, где <tex>\alpha \in (N')^+</tex> и <tex>\beta \in (N')^+</tex> и <tex>|\alpha| \leqslant |\beta|</tex>, или <tex>A \rightarrow a</tex>, или <tex>A \rightarrow \varepsilon</tex>, где <tex>A \in N'</tex> и <tex>a \in T</tex> |
* <tex>L(G') = L(G)</tex> | * <tex>L(G') = L(G)</tex> | ||
|proof= | |proof= | ||
Строка 83: | Строка 83: | ||
{{Определение | {{Определение | ||
− | |definition=Грамматика имеет '''порядок n''', если <tex>|\alpha| | + | |definition=Грамматика имеет '''порядок n''', если <tex>|\alpha| \leqslant n</tex> и <tex>|\beta| \leqslant n</tex> для любого ее правила <tex>\alpha \rightarrow \beta</tex>. |
}} | }} | ||
Строка 90: | Строка 90: | ||
|about=об уменьшении порядка грамматики | |about=об уменьшении порядка грамматики | ||
|statement=(Уменьшение порядка грамматики) | |statement=(Уменьшение порядка грамматики) | ||
− | Для любой грамматики <tex>G = (N, T, P, S)</tex> порядка <tex>n >= 3</tex>, такой что: любое правило из <tex>P'</tex> имеет вид <tex>\alpha \rightarrow \beta</tex>, где <tex>\alpha \in (N')^+</tex> и <tex>\beta \in (N')^+</tex> и <tex>|\alpha| | + | Для любой грамматики <tex>G = (N, T, P, S)</tex> порядка <tex>n >= 3</tex>, такой что: любое правило из <tex>P'</tex> имеет вид <tex>\alpha \rightarrow \beta</tex>, где <tex>\alpha \in (N')^+</tex> и <tex>\beta \in (N')^+</tex> и <tex>|\alpha| \leqslant |\beta|</tex> или <tex>A \rightarrow a</tex> или <tex>A \rightarrow \varepsilon</tex>, где <tex>A \in N'</tex> и <tex>a \in T</tex> может быть построена грамматика <tex>G' = (N', T, P', S)</tex> порядка <tex>n - 1</tex> такая, что <tex>L(G') = L(G)</tex>. |
|proof= | |proof= | ||
Разделим <tex>P</tex> на три подмножества: | Разделим <tex>P</tex> на три подмножества: | ||
− | <tex>P_1 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| | + | <tex>P_1 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| \leqslant 2, |\beta| \leqslant 2 \}</tex>, |
<tex>P_2 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| >= 2, |\beta| >= 3 \}</tex>, | <tex>P_2 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| >= 2, |\beta| >= 3 \}</tex>, |
Версия 14:03, 4 января 2015
Определение: |
Грамматика представлена в нормальной форме Куроды (англ. Kuroda normal form), если каждое правило имеет одну из четырех форм:
|
Данная грамматика названа в честь Куроды (англ. Sige-Yuki Kuroda), который изначально назвал ее линейно ограниченной грамматикой.
Определение: |
Грамматика представлена в нормальной форме Пенттонена (англ. Penttonen normal form), если каждое правило имеет одну из трех форм:
|
Также грамматику Пенттонена называют односторонней нормальной формой (англ. one-sided normal form). Как можно заметить, она является частным случаем нормальной формы Куроды: когда в первом правиле определения.
Для каждой контестно-зависимой грамматики существует слабо эквивалентная ей грамматика в форме Пенттонена.
Лемма (об удалении терминалов): |
Для любой грамматики может быть построена грамматика такая, что:
|
Доказательство: |
Каждому терминалу поставим в соотвествие новый символ , которого нет в , такой что для разных терминалов и .Пусть .Пусть — часть правила, тогда , где , если ; , если для .Построим грамматику , где .Покажем, что .Пусть . Тогда в G существует вывод .Согласно конструкции , в существует вывод .Для в переходах используем правило , так как правило было использовано при выводе .Для в переходах используем правила вида .Заменяем разрешенные в символы на новые и получаем, что . Тогда .Пусть . Тогда в существует вывод . Мы можем поменять порядок применения правил в этом выводе: сначала применяем только правила вида , а потом только правила вида .Из построения: после применения правила вида полученное не может быть использовано при применении правил из .Изменение порядка вывода не меняет язык, то есть в существует вывод: , где для и в переходе было использовано правило вывода и для было использовано правило , чтобы получить .Получаем вывод в : .Тогда .Таким образом, Очевидно, что если грамматика была неукорочивающейся, то она такой и останется. . |
Лемма (об удалении длинных правил): |
Для любой грамматики может быть построена грамматика такая, что:
|
Доказательство: |
Сначала по построим грамматику , как в доказательстве леммы 1. По построим грамматику , в которой:
Теперь все правила в имеет требуемую форму.Покажем, что .Заметим, что замена правила Тогда получаем, что на не меняет язык грамматики, потому что дополнительная буква запрещается при добавлении перехода , а других правил для нет. , аналогично обратные изменения не меняют язык, то есть . |
Определение: |
Грамматика имеет порядок n, если | и для любого ее правила .
Лемма (об уменьшении порядка грамматики): |
(Уменьшение порядка грамматики)
Для любой грамматики порядка , такой что: любое правило из имеет вид , где и и или или , где и может быть построена грамматика порядка такая, что . |
Доказательство: |
Разделим на три подмножества: ,, . Очевидно, что .Построим следующим образом:
Полагаем , , где — дополнительные символы не из для разных правил и из .
Полагаем , , где — дополнительные символы.Тогда , .Из построения очевидно, что имеет порядок .Покажем, что .Сначала докажем, что . Это следует из того, что:
, с использованием правил из и вывода на основе правила в , которое может быть применено в с помощью трех шагов вывода: . Таким образом, любой вывод в может быть преобразован в вывод в . Чтобы показать обратное включение, рассмотрим вывод в , который содержит применение правил вида для какого-то правила . Заметим, что другие два правила из могут быть применены только если правило было применено в этом выводе ранее.Данный вывод имеет вид (1) : ,где — последовательность правил, примененых после и до , которая осуществляет и ,где — последовательность правил, осуществляющих и .Или вид (2) : ,где — последовательность правил, которая осуществляет и ,где — последовательность правил, осуществляющих и .Таким образом, существует вывод: , который получается из (1) заменой правил на применение . Аналогично, в случае (2) мы можем заменить применение на . Кроме того, это верно и для применения где .Таким образом, для Тогда мы можем заменить все применения на , то есть получаем вывод , который состоит только из правил из . и . |
Теорема: |
Любую грамматику можно преобразовать к грамматике в нормальной форме Куроды так, что . |
Доказательство: |
По лемме 1 построим из грамматику , затем по лемме 2 построим из грамматику , Тогда удовлетворит требованиям леммы 3.Пусть Будем повторять процесс, пока не получим грамматику порядка имеет порядок . Если , то в нормальной форме Куроды и . Если , построим порядка из по лемме 3. Понятно, что удовлетворяет условиям леммы 3. , которую и примем за . |