Нормальная форма Куроды - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:29:36Z

rollbackEdits.php mass rollback

80.82.78.13 в 04:38, 1 сентября 2022

2022-09-01T04:38:26Z

Tindarid в 18:23, 30 марта 2018

2018-03-30T18:23:48Z

Tindarid в 18:22, 30 марта 2018

2018-03-30T18:22:45Z

KK в 18:30, 21 декабря 2015

2015-12-21T18:30:30Z

Внесённые изменения

Shersh в 10:45, 15 января 2015

2015-01-15T10:45:56Z

Shersh в 12:19, 11 января 2015

2015-01-11T12:19:53Z

178.71.128.115: /* Источники информации */

2015-01-04T14:41:59Z

‎Источники информации

178.71.128.115 в 14:40, 4 января 2015

2015-01-04T14:40:25Z

178.71.128.115 в 14:35, 4 января 2015

2015-01-04T14:35:30Z

← Предыдущая		Версия 16:29, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	{{Определение		{{Определение
	\|definition=[[Формальные грамматики\|Грамматика]] представлена в '''нормальной форме Куроды''' (англ. ''Kuroda normal form''), если каждое правило имеет одну из четырех форм:		\|definition=[[Формальные грамматики\|Грамматика]] представлена в '''нормальной форме Куроды''' (англ. ''Kuroda normal form''), если каждое правило имеет одну из четырех форм:

← Предыдущая		Версия 04:38, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	{{Определение		{{Определение
	\|definition=[[Формальные грамматики\|Грамматика]] представлена в '''нормальной форме Куроды''' (англ. ''Kuroda normal form''), если каждое правило имеет одну из четырех форм:		\|definition=[[Формальные грамматики\|Грамматика]] представлена в '''нормальной форме Куроды''' (англ. ''Kuroda normal form''), если каждое правило имеет одну из четырех форм:

@@ Строка 42: / Строка 42: @@
 Покажем, что <tex>L(\Gamma') = L(\Gamma)</tex>.
-Пусть <tex>w \in L(\Gamma)</tex>. Тогда в <tex>\Gamma</tex> существует вывод <tex>S = w_0 \Rightarrow w_1 \Rightarrow ... \Rightarrow w_n \Rightarrow w</tex>.
+Пусть <tex>w \in L(\Gamma)</tex>. Тогда в <tex>\Gamma</tex> существует вывод <tex>S = w_0 \Rightarrow w_1 \Rightarrow \ldots \Rightarrow w_n \Rightarrow w</tex>.
-Согласно конструкции <tex>P'</tex>, в <tex>\Gamma'</tex> существует вывод <tex>S = w_0' \Rightarrow w_1' \Rightarrow w_2' \Rightarrow ... \Rightarrow w_n' = v_0 \Rightarrow v_1 \Rightarrow v_2 \Rightarrow ... \Rightarrow v_m = w</tex>.
+Согласно конструкции <tex>P'</tex>, в <tex>\Gamma'</tex> существует вывод <tex>S = w_0' \Rightarrow w_1' \Rightarrow w_2' \Rightarrow \ldots \Rightarrow w_n' = v_0 \Rightarrow v_1 \Rightarrow v_2 \Rightarrow \ldots \Rightarrow v_m = w</tex>.
 Для <tex>0 \leqslant i \leqslant n - 1</tex> в переходах <tex>w_i' \Rightarrow w_{i + 1}'</tex> используем правило <tex>\alpha' \rightarrow \beta'</tex>, так как правило <tex>\alpha \rightarrow \beta</tex> было использовано при выводе <tex>w_i \Rightarrow w_{i + 1}</tex>.

@@ Строка 30: / Строка 30: @@
 Пусть <tex>N' = N \cup \{a' \mid a \in \Sigma\}</tex>.
-Пусть <tex>\alpha = x_1x_2...x_n</tex> {{---}} часть правила, тогда <tex>\alpha' = y_1y_2...y_n</tex>, где
+Пусть <tex>\alpha = x_1x_2 \ldots x_n</tex> {{---}} часть правила, тогда <tex>\alpha' = y_1y_2 \ldots y_n</tex>, где
 <tex>
 y_i = \left\{\begin{array}{llcl}
@@ Строка 57: / Строка 57: @@
 Из построения: после применения правила вида <tex>a' \rightarrow a</tex> полученное <tex>a</tex> не может быть использовано при применении правил из <tex>P'</tex>.
-Изменение порядка вывода не меняет язык, то есть в <tex>\Gamma'</tex> существует вывод: <tex>S = x_0' \Rightarrow x_1' \Rightarrow ... \Rightarrow x_r' \Rightarrow x' \Rightarrow y_1 \Rightarrow y_2 \Rightarrow ... \Rightarrow 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>\Gamma'</tex> существует вывод: <tex>S = x_0' \Rightarrow x_1' \Rightarrow \ldots \Rightarrow x_r' \Rightarrow x' \Rightarrow y_1 \Rightarrow y_2 \Rightarrow \ldots \Rightarrow 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>\Gamma</tex>: <tex>S = x_0 \Rightarrow x_1 \Rightarrow ... \Rightarrow x_n = x</tex>.
+Получаем вывод в <tex>\Gamma</tex>: <tex>S = x_0 \Rightarrow x_1 \Rightarrow \ldots \Rightarrow x_n = x</tex>.
 Тогда <tex>L(\Gamma') \subseteq L(\Gamma)</tex>.

@@ Строка 115: / Строка 115: @@
 Полагаем <tex>N_p = \{B_p \}</tex>, <tex>P_p = \{A \rightarrow CB_p, B_p \rightarrow DE\beta'\}</tex>, где <tex>A_p, B_p</tex> {{---}} дополнительные символы.
-Тогда <tex>N' = N \bigcup_{p \in (P_2 \cup P_3)} N_p</tex>, <tex>P' = P_1 \bigcup_{p \in (P_2 \cup P_3)} P_p</tex>.
+Тогда <tex>N' = N \bigcup\limits_{p \in (P_2 \cup P_3)} N_p</tex>, <tex>P' = P_1 \bigcup\limits_{p \in (P_2 \cup P_3)} P_p</tex>.
 Из построения очевидно, что <tex>G'</tex> имеет порядок <tex>n - 1</tex>.

@@ Строка 24: / Строка 24: @@
 * все правила в <tex>P'</tex> имеет вид <tex>\alpha \rightarrow \beta</tex> где <tex>\alpha \in (N')^+</tex> и <tex>\beta \in (N')^*</tex> или <tex>A \rightarrow a</tex>, где <tex>A \in N', a \in \Sigma</tex>,
 * <tex>L(G') = L(G)</tex>
-Кроме того, если G контекстно-свободна или контекстно-зависима, то и <tex>G'</tex> будет соответственно контекстно-свободной или контекстно-зависимой.
+Кроме того, если <tex>G</tex> контекстно-свободна или контекстно-зависима, то и <tex>G'</tex> будет соответственно контекстно-свободной или контекстно-зависимой.
 |proof = Каждому терминалу <tex>a</tex> поставим в соотвествие новый символ <tex>a'</tex>, которого нет в <tex>N \cup \Sigma</tex>, такой что <tex>a' \neq b'</tex> для разных терминалов <tex>a</tex> и <tex>b</tex>.

← Предыдущая		Версия 14:41, 4 января 2015
Строка 174:		Строка 174:
	* [[wikipedia:Kuroda_normal_form \| Wikipedia {{---}} Kuroda normal form]]		* [[wikipedia:Kuroda_normal_form \| Wikipedia {{---}} Kuroda normal form]]

−	[[Категория: Теория формальных языков]]	+	[[Категория: Теория формальных языков]] [[Категория: Контекстно-свободные грамматики ]] [[Категория: Нормальные формы КС-грамматик ]]

@@ Строка 57: / Строка 57: @@
 Из построения: после применения правила вида <tex>a' \rightarrow a</tex> полученное <tex>a</tex> не может быть использовано при применении правил из <tex>P'</tex>.
-Изменение порядка вывода не меняет язык, то есть в <tex>G'</tex> существует вывод: <tex>S = x_0' \Rightarrow x_1' \Rightarrow ... \Rightarrow x_r' \Rightarrow x' \Rightarrow y_1 \Rightarrow y_2 \Rightarrow ... \Rightarrow 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' \Rightarrow x_1' \Rightarrow ... \Rightarrow x_r' \Rightarrow x' \Rightarrow y_1 \Rightarrow y_2 \Rightarrow ... \Rightarrow 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 \Rightarrow x_1 \Rightarrow ... \Rightarrow x_n = x</tex>.
@@ Строка 68: / Строка 68: @@
 {{Лемма
-|about=об удалении длинных правил
+|about=об удалении коротких правил
 |statement= Для любой грамматики <tex>G = \langle \Sigma, N, S, P \rangle</tex> может быть построена грамматика  <tex>G' = \langle \Sigma, N', S, P' \rangle</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>
@@ Строка 81: / Строка 81: @@
 Покажем, что <tex>L(G') = L(G)</tex>.
-Заметим, что замена правила <tex>\alpha \rightarrow \beta</tex> на <tex>\alpha \rightarrow \beta D^{|\alpha| - |\beta|}</tex> не меняет язык грамматики, потому что дополнительная буква <tex>D</tex> запрещается при добавлении перехода <tex>D \rightarrow \varepsilon</tex>, а других правил для <tex>D</tex> нет.
+Заметим, что замена правила <tex>\alpha \rightarrow \beta</tex> на <tex>\alpha \rightarrow \beta D^{|\alpha| - |\beta|}</tex> не меняет язык грамматики, потому что <tex>D</tex> переходит только в <tex>\varepsilon</tex>, а других правил для <tex>D</tex> нет.
 Тогда получаем, что <tex>L(G) \subseteq L(G')</tex>, аналогично обратные изменения не меняют язык, то есть <tex>L(G') \subseteq L(G)</tex>.
@@ Строка 93: / Строка 93: @@
 {{Лемма
 |about=об уменьшении порядка грамматики
-|statement=(Уменьшение порядка грамматики)
+|statement=
 Для любой грамматики <tex>G = \langle \Sigma, N, S, P \rangle</tex> порядка <tex>n \geqslant 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' = \langle \Sigma, N', S, P' \rangle</tex> порядка <tex>n - 1</tex> такая, что <tex>L(G') = L(G)</tex>.
 |proof=
@@ Строка 170: / Строка 170: @@
 * [[Приведение_грамматики_к_ослабленной_нормальной_форме_Грейбах|Приведение грамматики к ослабленной нормальной форме Грейбах]]
-== Источники ==
+== Источники информации ==
 * Alexander Meduna Automata and Languages: Theory and Applications
 * [[wikipedia:Kuroda_normal_form | Wikipedia {{---}} Kuroda normal form]]
 [[Категория: Теория формальных языков]]

@@ Строка 28: / Строка 28: @@
 |proof = Каждому терминалу <tex>a</tex> поставим в соотвествие новый символ <tex>a'</tex>, которого нет в <tex>N \cup \Sigma</tex>, такой что <tex>a' \neq b'</tex> для разных терминалов <tex>a</tex> и <tex>b</tex>.
-Пусть <tex>N' = N \cup \{a' : a \in \Sigma\}</tex>.
+Пусть <tex>N' = N \cup \{a' \mid a \in \Sigma\}</tex>.
 Пусть <tex>\alpha = x_1x_2...x_n</tex> {{---}} часть правила, тогда <tex>\alpha' = y_1y_2...y_n</tex>, где
@@ Строка 38: / Строка 38: @@
 </tex> для <tex>1 \leqslant i \leqslant n</tex>.
-Построим грамматику <tex>G' = \langle \Sigma, N', S, P' \rangle</tex>, где <tex>P' = \{\alpha' \rightarrow \beta' : \alpha \rightarrow \beta \in P\} \cup \{a' \rightarrow a: a \in \Sigma\}</tex>.
+Построим грамматику <tex>G' = \langle \Sigma, N', S, P' \rangle</tex>, где <tex>P' = \{\alpha' \rightarrow \beta' \mid \alpha \rightarrow \beta \in P\} \cup \{a' \rightarrow a \mid a \in \Sigma\}</tex>.
 Покажем, что <tex>L(G') = L(G)</tex>.
@@ Строка 98: / Строка 98: @@
 Разделим <tex>P</tex> на три подмножества:
-<tex>P_1 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| \leqslant 2, |\beta| \leqslant 2 \}</tex>,
+<tex>P_1 = \{ \alpha \rightarrow \beta \mid \alpha \rightarrow \beta \in P, |\alpha| \leqslant 2, |\beta| \leqslant 2 \}</tex>,
-<tex>P_2 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| \geqslant 2, |\beta| \geqslant 3 \}</tex>,
+<tex>P_2 = \{ \alpha \rightarrow \beta \mid \alpha \rightarrow \beta \in P, |\alpha| \geqslant 2, |\beta| \geqslant 3 \}</tex>,
-<tex>P_3 = \{ \alpha \rightarrow \beta | \alpha \rightarrow \beta \in P, |\alpha| = 1, |\beta| \geqslant 3 \}</tex>.
+<tex>P_3 = \{ \alpha \rightarrow \beta \mid \alpha \rightarrow \beta \in P, |\alpha| = 1, |\beta| \geqslant 3 \}</tex>.
 Очевидно, что <tex>P = P_1 \cup P_2 \cup P_3</tex>.