Викиконспекты - Вклад участника [ru]

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-14T21:12:50Z

Sergey.melnikov:

{{Определение
|definition = Грамматика называется '''неукорачивающей''', если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex> (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}

{{Определение
|definition = Грамматика называется '''контекстно-зависимой''', если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}

{{Теорема
|statement=Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.
|proof=

Рассмотрим правило из <tex>\Gamma_1</tex>, оно имеет вид <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge n</tex>
добавим в <tex>\Gamma_2</tex> следующий набор правил:

<tex>
\begin{tabular}{rcl}
$X_1 X_2 X_3 \ldots X_n$ & $\to$&$ Z_1 X_2 X_3 \ldots X_n$\\
$Z_1 X_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 X_3 \ldots X_n$\\
$Z_1 Z_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 Z_3 \ldots X_n$\\
&$\ldots$&\\
$Z_1 Z_2 \ldots Z_{n-1} X_n$ &$\to$& $Z_1 Z_2 \ldots Z_{n-1} Z_n$\\
$Z_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Z_2 Z_3 \ldots Z_n$\\
$Y_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Z_3 \ldots Z_n$\\
$Y_1 Y_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Y_3 \ldots Z_n$\\
&$\ldots$&\\
$Y_1 Y_2 Y_3 \ldots Y_{n-1} Z_n$&$\to$& $Y_1 Y_2 Y_3 \ldots Y_{n-1} Y_n \ldots Y_m$\\
\end{tabular}
</tex>

Где нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex>

В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 X_2 \ldots X_n</tex>, то в последствии должны быть применены все остальные правила. В противном случае нетерминалы <tex>Z_1</tex> или <tex>Z_n</tex> будут присутствовать в выведенном слове.

Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения набора правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку <tex>Y_1 Y_2 \ldots Y_m</tex>. Каждый набор правил либо будет применён полностью, либо не будет применён полностью

Получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.
}}
{{Утверждение
|statement=Любая контекстно-зависимая грамматика является неукорачивающей.
|proof= Так как в определении контекстно-зависимой грамматики <tex>\gamma</tex> не пуста, то <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>, а поэтому эта грамматика является неукорачивающей.
}}

Таким образом, из того что по любой неукорачивающей грамматике можно построить эквивалентную ей контекстно-зависимую, а также любая контекстно-зависимая грамматика является неукорачивающей, следует, что множества языков задаваемых этими видами грамматик совпадают.

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-14T21:05:10Z

Sergey.melnikov:

{{Определение
|definition = Грамматика '''неукорачивающая''', если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex> (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}

{{Определение
|definition = Грамматика '''контекстно-зависимая''', если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}

{{Теорема
|statement=Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.
|proof=

Рассмотрим правило из <tex>\Gamma_1</tex>, оно имеет вид <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge n</tex>
добавим в <tex>\Gamma_2</tex> следующий набор правил:

<tex>
\begin{tabular}{rcl}
$X_1 X_2 X_3 \ldots X_n$ & $\to$&$ Z_1 X_2 X_3 \ldots X_n$\\
$Z_1 X_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 X_3 \ldots X_n$\\
$Z_1 Z_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 Z_3 \ldots X_n$\\
&$\ldots$&\\
$Z_1 Z_2 \ldots Z_{n-1} X_n$ &$\to$& $Z_1 Z_2 \ldots Z_{n-1} Z_n$\\
$Z_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Z_2 Z_3 \ldots Z_n$\\
$Y_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Z_3 \ldots Z_n$\\
$Y_1 Y_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Y_3 \ldots Z_n$\\
&$\ldots$&\\
$Y_1 Y_2 Y_3 \ldots Y_{n-1} Z_n$&$\to$& $Y_1 Y_2 Y_3 \ldots Y_{n-1} Y_n \ldots Y_m$\\
\end{tabular}
</tex>

Где нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex>

В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 X_2 \ldots X_n</tex>, то в последствии должны быть применены все остальные правила. В противном случае нетерминалы <tex>Z_1</tex> или <tex>Z_n</tex> будут присутствовать в выведенном слове.

Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения набора правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку <tex>Y_1 Y_2 \ldots Y_m</tex>. Каждый набор правил либо будет применён полностью, либо не будет применён полностью

Получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.
}}
{{Утверждение
|statement=Любая контекстно-зависимая грамматика является неукорачивающей.
|proof= Так как в определении контекстно-зависимой грамматики <tex>\gamma</tex> не пуста, то <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>, а поэтому эта грамматика является неукорачивающей.
}}

Таким образом, из того что по любой неукорачивающей грамматике можно построить эквивалентную ей контекстно-зависимую, а также любая контекстно-зависимая грамматика является неукорачивающей, следует, что множества языков задаваемых этими видами грамматик совпадают.

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-14T21:04:29Z

Sergey.melnikov:

{{Определение
|definition = Грамматика '''неукорачивающая''', если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex> (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}

{{Определение
|definition = Грамматика '''контекстно-зависимая''', если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}

{{Теорема
|statement=Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.
|proof=

Рассмотрим правило из <tex>\Gamma_1</tex>, оно имеет вид <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge n</tex>
добавим в <tex>\Gamma_2</tex> следующий набор правил:

<tex>
\begin{tabular}{rcl}
$X_1 X_2 X_3 \ldots X_n$ & $\to$&$ Z_1 X_2 X_3 \ldots X_n$\\
$Z_1 X_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 X_3 \ldots X_n$\\
$Z_1 Z_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 Z_3 \ldots X_n$\\
&$\ldots$&\\
$Z_1 Z_2 \ldots Z_{n-1} X_n$ &$\to$& $Z_1 Z_2 \ldots Z_{n-1} Z_n$\\
$Z_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Z_2 Z_3 \ldots Z_n$\\
$Y_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Z_3 \ldots Z_n$\\
$Y_1 Y_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Y_3 \ldots Z_n$\\
&$\ldots$&\\
$Y_1 Y_2 Y_3 \ldots Y_{n-1} Z_n$&$\to$& $Y_1 Y_2 Y_3 \ldots Y_{n-1} Y_n \ldots Y_m$\\
\end{tabular}
</tex>

Где нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex>

В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 Y_2 \ldots Y_m</tex>, то в последствии должны быть применены все остальные правила. В противном случае нетерминалы <tex>Z_1</tex> или <tex>Z_n</tex> будут присутствовать в выведенном слове.

Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения набора правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку <tex>Y_1 Y_2 \ldots Y_m</tex>. Каждый набор правил либо будет применён полностью, либо не будет применён полностью

Получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.
}}
{{Утверждение
|statement=Любая контекстно-зависимая грамматика является неукорачивающей.
|proof= Так как в определении контекстно-зависимой грамматики <tex>\gamma</tex> не пуста, то <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>, а поэтому эта грамматика является неукорачивающей.
}}

Таким образом, из того что по любой неукорачивающей грамматике можно построить эквивалентную ей контекстно-зависимую, а также любая контекстно-зависимая грамматика является неукорачивающей, следует, что множества языков задаваемых этими видами грамматик совпадают.

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-14T21:03:02Z

Sergey.melnikov:

{{Определение
|definition = Грамматика '''неукорачивающая''', если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex> (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}

{{Определение
|definition = Грамматика '''контекстно-зависимая''', если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}

{{Теорема
|statement=Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.
|proof=

Рассмотрим правило из <tex>\Gamma_1</tex>, оно имеет вид <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge n</tex>
добавим в <tex>\Gamma_2</tex> следующий набор правил:

<tex>
\begin{tabular}{rcl}
$X_1 X_2 X_3 \ldots X_n$ & $\to$&$ Z_1 X_2 X_3 \ldots X_n$\\
$Z_1 X_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 X_3 \ldots X_n$\\
$Z_1 Z_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 Z_3 \ldots X_n$\\
&$\ldots$&\\
$Z_1 Z_2 \ldots Z_{n-1} X_n$ &$\to$& $Z_1 Z_2 \ldots Z_{n-1} Z_n$\\
$Z_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Z_2 Z_3 \ldots Z_n$\\
$Y_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Z_3 \ldots Z_n$\\
$Y_1 Y_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Y_3 \ldots Z_n$\\
&$\ldots$&\\
$Y_1 Y_2 Y_3 \ldots Y_{n-1} Z_n$&$\to$& $Y_1 Y_2 Y_3 \ldots Y_{n-1} Y_n \ldots Y_m$\\
\end{tabular}
</tex>

Где нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex>

В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 Y_2 \ldots Y_m</tex>, то в последствии должны быть применены все остальные правила. В противном случае нетерминалы <tex>Z_1</tex> или <tex>Z_n</tex> будут присутствовать в выведенном слове.

Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку <tex>Y_1 Y_2 \ldots Y_m</tex>. Каждый набор правил либо будет применён полностью, либо не будет применён полностью

Получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.
}}
{{Утверждение
|statement=Любая контекстно-зависимая грамматика является неукорачивающей.
|proof= Так как в определении контекстно-зависимой грамматики <tex>\gamma</tex> не пуста, то <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>, а поэтому эта грамматика является неукорачивающей.
}}

Таким образом, из того что по любой неукорачивающей грамматике можно построить эквивалентную ей контекстно-зависимую, а также любая контекстно-зависимая грамматика является неукорачивающей, следует, что множества языков задаваемых этими видами грамматик совпадают.

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-14T21:02:03Z

Sergey.melnikov:

{{Определение
|definition = Грамматика '''неукорачивающая''', если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex> (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}

{{Определение
|definition = Грамматика '''контекстно-зависимая''', если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}

{{Теорема
|statement=Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.
|proof=

Рассмотрим правило из <tex>\Gamma_1</tex>, оно имеет вид <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge n</tex>
добавим в <tex>\Gamma_2</tex> следующий набор правил:

<tex>
\begin{tabular}{rcl}
$X_1 X_2 X_3 \ldots X_n$ & $\to$&$ Z_1 X_2 X_3 \ldots X_n$\\
$Z_1 X_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 X_3 \ldots X_n$\\
$Z_1 Z_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 Z_3 \ldots X_n$\\
&$\ldots$&\\
$Z_1 Z_2 \ldots Z_{n-1} X_n$ &$\to$& $Z_1 Z_2 \ldots Z_{n-1} Z_n$\\
$Z_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Z_2 Z_3 \ldots Z_n$\\
$Y_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Z_3 \ldots Z_n$\\
$Y_1 Y_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Y_3 \ldots Z_n$\\
&$\ldots$&\\
$Y_1 Y_2 Y_3 \ldots Y_{n-1} Z_n$&$\to$& $Y_1 Y_2 Y_3 \ldots Y_{n-1} Y_n \ldots Y_m$\\
\end{tabular}
</tex>

Где нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex>

В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 Y_2 \ldots Y_m</tex>, то в последствии должны быть применены все остальные правила. В противном случае нетерминалы <tex>Z_1</tex> или <tex>Z_n</tex> будут присутствовать в выведенном слове.

Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку <tex>Y_1 Y_2 \ldots Y_m</tex>. Каждый набор правил либо будет применён полностью, либо не будет применён полностью

Получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.
}}
{{Утверждение
|statement=Любая контекстно-зависимая грамматика является неукорачивающей.
|proof= Так как в определении контекстно-зависимой грамматики <tex>\gamma</tex> не пуста, то <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>, а поэтому эта грамматика является неукорачивающей.
}}

Таким образом, из того что по любой неукорачивающей грамматике можно построить эквивалентную ей контекстно-зависимую, и наоборот любая контекстно-зависимая грамматика является неукорачивающей, следует, что множества языков задаваемых этими видами грамматик совпадают.

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-14T20:54:33Z

Sergey.melnikov:

{{Определение
|definition = Грамматика '''неукорачивающая''', если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex> (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}

{{Определение
|definition = Грамматика '''контекстно-зависимая''', если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}

{{Теорема
|statement=Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.
|proof=

Рассмотрим правило из <tex>\Gamma_1</tex>, оно имеет вид <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge n</tex>
добавим в <tex>\Gamma_2</tex> следующий набор правил:

<tex>
\begin{tabular}{rcl}
$X_1 X_2 X_3 \ldots X_n$ & $\to$&$ Z_1 X_2 X_3 \ldots X_n$\\
$Z_1 X_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 X_3 \ldots X_n$\\
$Z_1 Z_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 Z_3 \ldots X_n$\\
&$\ldots$&\\
$Z_1 Z_2 \ldots Z_{n-1} X_n$ &$\to$& $Z_1 Z_2 \ldots Z_{n-1} Z_n$\\
$Z_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Z_2 Z_3 \ldots Z_n$\\
$Y_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Z_3 \ldots Z_n$\\
$Y_1 Y_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Y_3 \ldots Z_n$\\
&$\ldots$&\\
$Y_1 Y_2 Y_3 \ldots Y_{n-1} Z_n$&$\to$& $Y_1 Y_2 Y_3 \ldots Y_{n-1} Y_n \ldots Y_m$\\
\end{tabular}
</tex>

Где нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex>

В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 Y_2 \ldots Y_m</tex>, то в последствии должны быть применены все остальные правила. В противном случае нетерминал <tex>Z_1</tex> или <tex>Z_n</tex> не исчезнут из слова.

Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку <tex>Y_1 Y_2 \ldots Y_m</tex>. Каждый набор правил либо будет применён полностью, либо не будет применён полностью

Получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.

Любая контекстно-зависимая грамматика является неукорачивающей, так как <tex>\gamma</tex> не пуста, а поэтому <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>.

Вывод: множества языков задаваемые неукорачивающими и контекстно-зависимыми грамматиками совпадают.
}}

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-14T20:53:21Z

Sergey.melnikov:

{{Определение
|definition = Грамматика '''неукорачивающая''', если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex> (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}

{{Определение
|definition = Грамматика '''контекстно-зависимая''', если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}

{{Теорема
|statement=Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.
|proof=

Рассмотрим правило из <tex>\Gamma_1</tex>, оно имеет вид <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge n</tex>
добавим в <tex>\Gamma_2</tex> следующий набор правил:

<tex>
\begin{tabular}{rcl}
$X_1 X_2 X_3 \ldots X_n$ & $\to$&$ Z_1 X_2 X_3 \ldots X_n$\\
$Z_1 X_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 X_3 \ldots X_n$\\
$Z_1 Z_2 X_3 \ldots X_n$ & $\to$& $Z_1 Z_2 Z_3 \ldots X_n$\\
&$\ldots$&\\
$Z_1 Z_2 \ldots Z_{n-1} X_n$ &$\to$& $Z_1 Z_2 \ldots Z_{n-1} Z_n$\\
$Z_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Z_2 Z_3 \ldots Z_n$\\
$Y_1 Z_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Z_3 \ldots Z_n$\\
$Y_1 Y_2 Z_3 \ldots Z_n$ &$\to$& $Y_1 Y_2 Y_3 \ldots Z_n$\\
&$\ldots$&\\
$Y_1 Y_2 Y_3 \ldots Y_{n-1} Z_n$&$\to$& $Y_1 Y_2 Y_3 \ldots Y_{n-1} Y_n \ldots Y_m$\\
\end{tabular}
</tex>

Где нетерминалы <tex>$Z_{*}$</tex> свои для каждого правила из <tex>\Gamma_1</tex>

В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>$X_1 X_2 \ldots X_n \to Z_1 Y_2 \ldots Y_m$</tex>, то в последствии должны быть применены все остальные правила. В противном случае нетерминал <tex>$Z_1$</tex> или <tex>$Z_n$</tex> не исчезнут из слова.

Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения правил строка <tex>$X_1 X_2 \ldots X_n$</tex> перейдёт в строку <tex>$Y_1 Y_2 \ldots Y_m$</tex>. Каждый набор правил либо будет применён полность, либо не будет применён полностью

Получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.

Любая контекстно-зависимая грамматика является неукорачивающей, так как <tex>\gamma</tex> не пуста, а поэтому <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>.

Вывод: множества языков задаваемые неукорачивающими и контекстно-зависимыми грамматиками совпадают.
}}

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-14T20:42:24Z

Sergey.melnikov:

{{Определение
|definition = Грамматика '''неукорачивающая''', если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex> (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}

{{Определение
|definition = Грамматика '''контекстно-зависимая''', если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}

{{Теорема
|statement=Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.
|proof=

Рассмотрим правило из <tex>\Gamma_1</tex>, оно имеет вид <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge n</tex>
добавим в <tex>\Gamma_2</tex> следующий набор правил:

<tex>X_1 X_2 X_3 \ldots X_n \to Z_1 X_2 X_3 \ldots X_n</tex>

<tex>Z_1 X_2 X_3 \ldots X_n \to Z_1 Z_2 X_3 \ldots X_n</tex>

<tex>Z_1 Z_2 X_3 \ldots X_n \to Z_1 Z_2 Z_3 \ldots X_n</tex>

<tex>\ldots</tex>

<tex>Z_1 Z_2 \ldots Z_{n-1} X_n \to Z_1 Z_2 \ldots Z_{n-1} Z_n</tex>

<tex>Z_1 Z_2 Z_3 \ldots Z_n \to Y_1 Z_2 Z_3 \ldots Z_n</tex>

<tex>Y_1 Z_2 Z_3 \ldots Z_n \to Y_1 Y_2 Z_3 \ldots Z_n</tex>

<tex>Y_1 Y_2 Z_3 \ldots Z_n \to Y_1 Y_2 Y_3 \ldots Z_n</tex>

<tex>\ldots</tex>

<tex>Y_1 Y_2 Y_3 \ldots Y_{n-1} Z_n \to Y_1 Y_2 Y_3 \ldots Y_{n-1} Y_n \ldots Y_m</tex>

Где нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex>

В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 Y_2 \ldots Y_m</tex>, то в последствии должны быть применены все остальные правила. В противном случае нетерминал <tex>Z_1</tex> или <tex>Z_n</tex> не исчезнут из слова.

Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку <tex>Y_1 Y_2 \ldots Y_m</tex>. Каждый набор правил либо будет применён полность, либо не будет применён полностью

Получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.

Любая контекстно-зависимая грамматика является неукорачивающей, так как <tex>\gamma</tex> не пуста, а поэтому <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>.

Вывод: множества языков задаваемые неукорачивающими и контекстно-зависимыми грамматиками совпадают.
}}

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-14T20:37:21Z

Sergey.melnikov:

{{Определение
|definition = Грамматика '''неукорачивающая''', если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex> (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}

{{Определение
|definition = Грамматика '''контекстно-зависимая''', если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда <tex>$S$</tex> не встречается в правых частях правил).
}}

{{Теорема
|statement=Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.
|proof=

Рассмотрим правило из <tex>\Gamma_1</tex>, оно имеет вид <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge n</tex>
добавим в <tex>\Gamma_2</tex> следующий набор правил:

<tex>X_1 X_2 \ldots X_n \to Z_1 X_2 \ldots X_n</tex>

<tex>Z_1 X_2 \ldots X_n \to Z_1 Z_2 \ldots X_n</tex>

<tex>\ldots</tex>

<tex>Z_1 Z_2 \ldots Z_{n-1} X_n \to Z_1 Z_2 \ldots Z_{n-1} Z_n</tex>

<tex>Z_1 \ldots Z_n \to Y_1 Z_2 \ldots Z_n</tex>

<tex>\ldots</tex>

<tex>Y_1 Y_2 \ldots Y_{n-1} Z_n \to Y_1 Y_2 \ldots Y_{n-1} Y_n \ldots Y_m</tex>

Где нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex>

В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 Y_2 \ldots Y_m</tex>, то в последствии должны быть применены все остальные правила. В противном случае нетерминал <tex>Z_1</tex> или <tex>Z_n</tex> не исчезнут из слова.

Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку <tex>Y_1 Y_2 \ldots Y_m</tex>. Каждый набор правил либо будет применён полность, либо не будет применён полностью

Получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.

Любая контекстно-зависимая грамматика является неукорачивающей, так как <tex>\gamma</tex> не пуста, а поэтому <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>.

Вывод: множества языков задаваемые неукорачивающими и контекстно-зависимыми грамматиками совпадают.
}}

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-14T20:35:37Z

Sergey.melnikov:

{{Определение
|definition = Грамматика '''неукорачивающая''', если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex> (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда S не встречается в правых частях правил).
}}

{{Определение
|definition = Грамматика '''контекстно-зависимая''', если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда S не встречается в правых частях правил).
}}

{{Теорема
|statement=Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.
|proof=

Рассмотрим правило из <tex>\Gamma_1</tex>, оно имеет вид <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge n</tex>
добавим в <tex>\Gamma_2</tex> следующий набор правил:

<tex>X_1 X_2 \ldots X_n \to Z_1 X_2 \ldots X_n</tex>

<tex>Z_1 X_2 \ldots X_n \to Z_1 Z_2 \ldots X_n</tex>

<tex>\ldots</tex>

<tex>Z_1 Z_2 \ldots Z_{n-1} X_n \to Z_1 Z_2 \ldots Z_{n-1} Z_n</tex>

<tex>Z_1 \ldots Z_n \to Y_1 Z_2 \ldots Z_n</tex>

<tex>\ldots</tex>

<tex>Y_1 Y_2 \ldots Y_{n-1} Z_n \to Y_1 Y_2 \ldots Y_{n-1} Y_n \ldots Y_m</tex>

Где нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex>

В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 Y_2 \ldots Y_m</tex>, то в последствии должны быть применены все остальные правила. В противном случае нетерминал <tex>Z_1</tex> или <tex>Z_n</tex> не исчезнут из слова.

Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку <tex>Y_1 Y_2 \ldots Y_m</tex>. Каждый набор правил либо будет применён полность, либо не будет применён полностью

Получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.

Любая контекстно-зависимая грамматика является неукорачивающей, так как <tex>\gamma</tex> не пуста, а поэтому <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>.

Вывод: множества языков задаваемые неукорачивающими и контекстно-зависимыми грамматиками совпадают.
}}

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-14T20:35:04Z

Sergey.melnikov:

{{Определение
|definition = Грамматика '''неукорачивающая''', если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex> (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда S не встречается в правых частях правил).
}}

{{Определение
|definition = Грамматика '''контекстно-зависимая''', если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста (возможно правило <tex>$S$ \to \varepsilon</tex>, но тогда S не встречается в правых частях правил).
}}

{{Теорема
|statement=Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.
|proof=

Рассмотрим правило из <tex>\Gamma_1</tex>, оно имеет вид <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge n</tex>
добавим в <tex>\Gamma_2</tex> следующий набор правил:

<tex>X_1 X_2 \ldots X_n \to Z_1 X_2 \ldots X_n</tex>

<tex>Z_1 X_2 \ldots X_n \to Z_1 Z_2 \ldots X_n</tex>

<tex>\ldots</tex>

<tex>Z_1 Z_2 \ldots Z_{n-1} X_n \to Z_1 Z_2 \ldots Z_{n-1} Z_n</tex>

<tex>Z_1 \ldots Z_n \to Y_1 Z_2 \ldots Z_n</tex>

<tex>\ldots</tex>

<tex>Y_1 Y_2 \ldots Y_{n-1} Z_n \to Y_1 Y_2 \ldots Y_{n-1} Y_n \ldots Y_m</tex>

Где нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex>

В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 Y_2 \ldots Y_m</tex>, то в последствии должны быть применены все остальные правила. В противном случае нетерминал <tex>Z_1</tex> или <tex>Z_n</tex> не исчезнут из слова.

Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку <tex>Y_1 Y_2 \ldots Y_m</tex>. Каждый набор правил либо будет применён полность, либо не будет применён полностью

Получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.

Любая контекстно-зависимая грамматика является неукорачивающей, так как <tex>\gamma</tex> не пуста, а поэтому <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>.

Вывод: множества языков задаваемые неукорачивающими и контекстно-зависимыми грамматиками совпадают.
}}

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-14T20:33:17Z

Sergey.melnikov:

{{Определение
|definition = Грамматика '''неукорачивающая''', если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex> (возможно правило <tex>S -> \varepsilon</tex>, но тогда S не встречается в правых частях правил).
}}

{{Определение
|definition = Грамматика '''контекстно-зависимая''', если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста (возможно правило <tex>S -> \varepsilon</tex>, но тогда S не встречается в правых частях правил).
}}

{{Теорема
|statement=Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.
|proof=

Рассмотрим правило из <tex>\Gamma_1</tex>, оно имеет вид <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge n</tex>
добавим в <tex>\Gamma_2</tex> следующий набор правил:

<tex>X_1 X_2 \ldots X_n \to Z_1 X_2 \ldots X_n</tex>

<tex>Z_1 X_2 \ldots X_n \to Z_1 Z_2 \ldots X_n</tex>

<tex>\ldots</tex>

<tex>Z_1 Z_2 \ldots Z_{n-1} X_n \to Z_1 Z_2 \ldots Z_{n-1} Z_n</tex>

<tex>Z_1 \ldots Z_n \to Y_1 Z_2 \ldots Z_n</tex>

<tex>\ldots</tex>

<tex>Y_1 Y_2 \ldots Y_{n-1} Z_n \to Y_1 Y_2 \ldots Y_{n-1} Y_n \ldots Y_m</tex>

Где нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex>

В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 Y_2 \ldots Y_m</tex>, то в последствии должны быть применены все остальные правила. В противном случае нетерминал <tex>Z_1</tex> или <tex>Z_n</tex> не исчезнут из слова.

Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку <tex>Y_1 Y_2 \ldots Y_m</tex>. Каждый набор правил либо будет применён полность, либо не будет применён полностью

Получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.

Любая контекстно-зависимая грамматика является неукорачивающей, так как <tex>\gamma</tex> не пуста, а поэтому <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>.

Вывод: множества языков задаваемые неукорачивающими и контекстно-зависимыми грамматиками совпадают.
}}

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-13T17:47:11Z

Sergey.melnikov:

{{Определение
|definition = Грамматика '''неукорачивающая''', если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex> (возможно правило <tex>S -> \epsilon</tex>, но тогда S не встречается в правых частях правил).
}}

{{Определение
|definition = Грамматика '''контекстно-зависимая''', если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста (возможно правило <tex>S -> \epsilon</tex>, но тогда S не встречается в правых частях правил).
}}

{{Теорема
|statement=Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.
|proof=

Рассмотрим правило из <tex>\Gamma_1</tex>, оно имеет вид <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge n</tex>
добавим в <tex>\Gamma_2</tex> следующий набор правил:

<tex>X_1 X_2 \ldots X_n \to Z_1 X_2 \ldots X_n</tex>

<tex>Z_1 X_2 \ldots X_n \to Z_1 Z_2 \ldots X_n</tex>

<tex>\ldots</tex>

<tex>Z_1 Z_2 \ldots Z_{n-1} X_n \to Z_1 Z_2 \ldots Z_{n-1} Z_n</tex>

<tex>Z_1 \ldots Z_n \to Y_1 Z_2 \ldots Z_n</tex>

<tex>\ldots</tex>

<tex>Y_1 Y_2 \ldots Y_{n-1} Z_n \to Y_1 Y_2 \ldots Y_{n-1} Y_n \ldots Y_m</tex>

Где нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex>

В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 Y_2 \ldots Y_m</tex>, то в последствии должны быть применены все остальные правила. В противном случае нетерминал <tex>Z_1</tex> или <tex>Z_n</tex> не исчезнут из слова.

Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку <tex>Y_1 Y_2 \ldots Y_m</tex>. Каждый набор правил либо будет применён полность, либо не будет применён полностью

Получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.

Любая контекстно-зависимая грамматика является неукорачивающей, так как <tex>\gamma</tex> не пуста, а поэтому <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>.

Вывод: множества языков задаваемые неукорачивающими и контекстно-зависимыми грамматиками совпадают.
}}

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-13T17:44:27Z

Sergey.melnikov:

{{Определение
|definition = Грамматика '''неукорачивающая''', если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex>(возможно правило <tex>S -> \epsilon</tex>, но тогда S не встречается в правых частях правил).
}}

{{Определение
|definition = Грамматика '''контекстно-зависимая''', если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста(возможно правило <tex>S -> \epsilon</tex>, но тогда S не встречается в правых частях правил).
}}

{{Теорема
|statement=Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.
|proof=

Рассмотрим правило из <tex>\Gamma_1</tex>, оно имеет вид <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge n</tex>
добавим в <tex>\Gamma_2</tex> следующий набор правил:

<tex>X_1 X_2 \ldots X_n \to Z_1 X_2 \ldots X_n</tex>

<tex>Z_1 X_2 \ldots X_n \to Z_1 Z_2 \ldots X_n</tex>

<tex>\ldots</tex>

<tex>Z_1 Z_2 \ldots Z_{n-1} X_n \to Z_1 Z_2 \ldots Z_{n-1} Z_n</tex>

<tex>Z_1 \ldots Z_n \to Y_1 Z_2 \ldots Z_n</tex>

<tex>\ldots</tex>

<tex>Y_1 Y_2 \ldots Y_{n-1} Z_n \to Y_1 Y_2 \ldots Y_{n-1} Y_n \ldots Y_m</tex>

Где нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex>

В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 Y_2 \ldots Y_m</tex>, то в последствии должны быть применены все остальные правила. В противном случае нетерминал <tex>Z_1</tex> или <tex>Z_n</tex> не исчезнут из слова.

Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку <tex>Y_1 Y_2 \ldots Y_m</tex>. Каждый набор правил либо будет применён полность, либо не будет применён полностью

Получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.

Любая контекстно-зависимая грамматика является неукорачивающей, так как <tex>\gamma</tex> не пуста, а поэтому <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>.

Вывод: множества языков задаваемые неукорачивающими и контекстно-зависимыми грамматиками совпадают.
}}

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-13T17:41:53Z

Sergey.melnikov:

Грамматика неукорачивающая, если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex>(возможно правило <tex>S -> \epsilon</tex>, но тогда S не встречается в правых частях правил).

Грамматика контекстно-зависимая, если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста(возможно правило <tex>S -> \epsilon</tex>, но тогда S не встречается в правых частях правил).

Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.

Рассмотрим правило из <tex>\Gamma_1</tex>, оно имеет вид <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge n</tex>
добавим в <tex>\Gamma_2</tex> следующий набор правил:

<tex>X_1 X_2 \ldots X_n \to Z_1 X_2 \ldots X_n</tex>

<tex>Z_1 X_2 \ldots X_n \to Z_1 Z_2 \ldots X_n</tex>

<tex>\ldots</tex>

<tex>Z_1 Z_2 \ldots Z_{n-1} X_n \to Z_1 Z_2 \ldots Z_{n-1} Z_n</tex>

<tex>Z_1 \ldots Z_n \to Y_1 Z_2 \ldots Z_n</tex>

<tex>\ldots</tex>

<tex>Y_1 Y_2 \ldots Y_{n-1} Z_n \to Y_1 Y_2 \ldots Y_{n-1} Y_n \ldots Y_m</tex>

Где нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex>

В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 Y_2 \ldots Y_m</tex>, то в последствии должны быть применены все остальные правила. В противном случае нетерминал <tex>Z_1</tex> или <tex>Z_n</tex> не исчезнут из слова.

Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку <tex>Y_1 Y_2 \ldots Y_m</tex>. Каждый набор правил либо будет применён полность, либо не будет применён полностью

Получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.

Любая контекстно-зависимая грамматика является неукорачивающей, так как <tex>\gamma</tex> не пуста, а поэтому <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>.

Вывод: множества языков задаваемые неукорачивающими и контекстно-зависимыми грамматиками совпадают.

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-11T17:56:12Z

Sergey.melnikov:

Грамматика неукорачивающая, если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex>(возможно правило <tex>S -> \epsilon</tex>, но тогда S встречается в правых частях правил).

Грамматика контекстно-зависимая, если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\beta</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста.

Для любой неукорачивающей грамматики <tex>\Gamma_1</tex> существует эквивалентная контекстно-зависимая грамматика <tex>\Gamma_2</tex>.

Рассмотрим правило из <tex>\Gamma_1</tex>, оно имеет вид <tex>X_1 X_2 \ldots X_n \to Y_1 Y_2 \ldots Y_m</tex>, где <tex>m \ge n</tex>
добавим в <tex>\Gamma_2</tex> следующий набор правил:

<tex>X_1 X_2 \ldots X_n \to Z_1 Y_2 \ldots Y_m</tex>

<tex>Z_1 X_2 \ldots X_n \to Z_1 Z_2 \ldots Y_m</tex>

<tex>\ldots</tex>

<tex>Z_1 Z_2 \ldots Z_{n-1} X_n \to Z_1 Z_2 \ldots Z_{n-1} Z_n</tex>

<tex>Z_1 \ldots Z_n \to Y_1 Z_2 \ldots Z_n</tex>

<tex>\ldots</tex>

<tex>Y_1 Y_2 \ldots Y_{n-1} Z_n \to Y_1 Y_2 \ldots Y_{n-1} Y_n \ldots Y_m</tex>

Где нетерминалы <tex>Z_{*}</tex> свои для каждого правила из <tex>\Gamma_1</tex>

В словах языка задаваемого грамматикой не может быть нетерминалов, поэтому если в процессе вывода будет применено правило <tex>X_1 X_2 \ldots X_n \to Z_1 Y_2 \ldots Y_m</tex>, то в последствии должны быть применены все остальные правила. В противном случае нетерминал <tex>Z_1</tex> или <tex>Z_n</tex> не исчезнут из слова.

Получившаяся грамматика <tex>\Gamma_2</tex> является эквивалентной грамматике <tex>\Gamma_1</tex>, так в результате применения правил строка <tex>X_1 X_2 \ldots X_n</tex> перейдёт в строку <tex>Y_1 Y_2 \ldots Y_m</tex>. Каждый набор правил либо будет применён полность, либо не будет применён полностью

Получившаяся грамматика <tex>\Gamma_2</tex> является контекстно-зависимой.

Любая контекстно-зависимая грамматика является неукорачивающей, так как <tex>\gamma</tex> не пуста, а поэтому <tex>|\alpha A \beta| \ge |\alpha \gamma \beta|</tex>.

Вывод: множества языков задаваемые неукорачивающими и контекстно-зависимыми грамматиками совпадают.

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-11T17:28:06Z

Sergey.melnikov:

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-11T17:25:02Z

Sergey.melnikov:

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-11T17:23:32Z

Sergey.melnikov:

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-11T17:21:32Z

Sergey.melnikov:

Неукорачивающие и контекстно-зависимые грамматики, эквивалентность

2010-10-11T17:13:17Z

Sergey.melnikov: Новая страница: «Грамматика <tex>\Gamma</tex> - неукорачивающая, если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\…»

Грамматика <tex>\Gamma</tex> - неукорачивающая, если все правила имеют вид <tex>\alpha \to \beta</tex>, где <tex>|\alpha| \le |\beta|</tex>(возможно правило <tex>S -> \epsilon</tex>, но тогда S встречается в правых частях правил).

Грамматика <tex>\Gamma</tex> - контекстно-зависимая, если все правила имеют вид <tex>\alpha A \beta \to \alpha \gamma \beta</tex>, где <tex>A</tex> - нетерминал, <tex>\alpha</tex> и <tex>\alpha</tex> строки из нетерминалов, <tex>\gamma</tex> не пуста.

Решение уравнений в регулярных выражениях

2010-10-07T15:15:26Z

Sergey.melnikov:

==Решение уравнений в регулярных выражениях==
{{Утверждение
|statement=
Пусть уравнение имеет вид <tex>X = \alpha X + \beta</tex>, тогда:
если <tex>\varepsilon \notin \alpha \Rightarrow \alpha^{*} \beta</tex> — единственное решение. если <tex>\varepsilon \in \alpha \Rightarrow \alpha^{*}( \beta + \alpha)</tex> — решение для <tex>\forall \alpha</tex>
|proof=
<tex> 1) \varepsilon \notin \alpha </tex>. тогда <tex>\forall i: \alpha^{i} \beta \subset X </tex> для <tex>\forall L \Rightarrow \alpha^{*} \beta \subset X </tex>. Пусть <tex>\exists z \in X, z\notin \alpha^{*} \beta: z</tex> — самое короткое. <tex>z=z_\alpha z', </tex> где <tex>z_\alpha \in \alpha \Rightarrow z_\alpha \notin \varepsilon \Rightarrow z'</tex> — короче <tex>z \Rightarrow z' \in \alpha^{*} \beta \Rightarrow z \in \alpha^{*} \beta \Rightarrow X = \alpha^{*} \beta </tex>

<tex> 2) \varepsilon \in \alpha</tex>. предположим, что <tex> \alpha^{*}( \beta + \alpha) </tex> — решение, тогда <tex> \alpha^{*}( \beta + \alpha) </tex> подходит в <tex>X = \alpha X + \beta</tex>. Выберем в качестве <tex>L</tex> любой язык.

<tex>\Rightarrow \alpha^{*} ( \beta + L ) = \alpha \alpha^{*} ( \beta + L ) + \beta \alpha^{*} \beta + \alpha^{*} \alpha = \alpha^{+} \beta + \alpha^{*} L + \beta = \alpha^{*} \beta + \alpha^{*} L = \alpha^{*}( \beta + \alpha) </tex>. что и требовалось доказать

}}