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

Детерминированные автоматы с магазинной памятью, допуск по пустому стеку

2011-01-25T04:16:09Z

Smetannikov.Ivan: Новая страница: «{{Определение |definition = Определим детерминированный автомат с магазинной памятью, допуска…»

{{Определение
|definition =
Определим детерминированный автомат с магазинной памятью, допускающий по пустому стеку, как [[Детерминированные_автоматы_с_магазинной_памятью|детерминированный автомат с магазинной памятью]], у которого нет множества <tex>F</tex> допускающих состояний. Автомат заканчивает свою работу как только стек становится пустым. Определим для него множество допускающих слов <tex>N = \{\omega | (q_0,a_0,Z_0)\vdash^* (p,\epsilon,\epsilon)\}</tex>, где <tex>p</tex> {{---}} произвольное состояние.
}}
{{Определение
|definition =
Язык называется беспрефиксным, если для него верно следующее: для любой пары слов из этого языка ни одно из этих слов не является префиксом другого.
}}
{{Теорема
|statement=Язык <tex>L</tex> допускается ДМП-автоматом, допускающему по пустому стеку <tex>\Leftrightarrow</tex> Язык <tex>L</tex> допускается ДМП-автоматом, допускающему по допускающему состоянию и <tex>L</tex> {{---}} беспрефиксный.
|proof=
<tex>\Rightarrow</tex> 
Допустим, что <tex>L</tex> не беспрефиксный. Тогда <tex>\exists \omega_1, \omega_2 \in L : \omega_2 = \omega_1 \alpha</tex>. Попробуем допустить слово <tex>\omega_2</tex>. Тогда автомат остановится сразу после префикса <tex>\omega_1</tex>, т.к. <tex>\omega_1 \in L</tex>. Стек будет пустой, однако до конца слова <tex>\omega_2</tex> мы не дойдем, поэтому оно не допустится, хотя содержится в <tex>L</tex>. Получили противоречие, значит <tex>L</tex> {{---}} беспрефиксный. 
Построим по заданному ДМП-автомату с допуском по пустому стеку ДМП с допуском по допускающему состоянию. 
[[Файл:ДМП1.png]] 
<tex>\Leftarrow</tex> 
Задан ДМП-автомат с допуском по допускающему состоянию, язык <tex>L</tex> {{---}} беспрефиксный. Если автомат в какойто момент пришел в допускающее состояние, то дальше идти смысла нет, т.к. тогда бы слово, допускаемое этим состоянием было бы префиксом некоторого другого слова. Значит можем удалить все переходы из допускающих состояний и добавить переходы в очистку стека. 
[[Файл:ДМП2.png]]
}}

Файл:ДМП2.png

2011-01-25T04:15:06Z

Smetannikov.Ivan:

Файл:ДМП1.png

2011-01-25T04:01:01Z

Smetannikov.Ivan:

Детерминированные автоматы с магазинной памятью

2011-01-23T18:32:09Z

Smetannikov.Ivan:

{{Определение
|definition =
Определим <tex>P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)</tex> как автомат с магазинной (стековой) памятью, где 
* <tex>Q</tex>: конечное множество состояний.
* <tex>\Sigma</tex>: конечное множество входных символов.
* <tex>\Gamma</tex>: конечный магазинный алфавит {{---}} множество символов, которые можно помещать в магазин.
* <tex>\delta</tex>: функция переходов. <tex>\delta (q,a,X)=(p,\gamma)</tex>, где
** <tex>q</tex>: текущее состояние из Q.
** <tex>a</tex>: входной символ или <tex>\epsilon</tex>.
** <tex>X</tex>: магазинный символ из <tex>\Gamma</tex>.
** <tex>p</tex>: новое состояние из Q.
** <tex>\gamma</tex>: цепочка магазинных символов, замещающих <tex>X</tex> на вершине магазина.
* <tex>q_0</tex>: начальное состояние.
* <tex>Z_0</tex>: начальный магазинный символ (маркер дна). Находится в магазине в начале работы автомата.
* <tex>F</tex>: множество допускающих состояний.
}}
{{Определение
|definition =
Определим детерминированный автомат с магазинной (стековой) памятью как автомат с магазинной памятью, в котором 
#<tex>\delta (q,a,X)</tex> имеет не более одного элемента для каждого <tex>q \in Q, a \in \Sigma</tex> или <tex>a=\epsilon, X \in \Gamma</tex>.
#Если <tex>\delta (q,a,X)</tex> непусто для некоторого <tex>a \in \Sigma</tex>, то <tex>\delta (q,\epsilon,X)</tex> должно быть пустым.
}}
Будем обозначать переход автомата из состояния <tex>(q_1,a_1,X_1)</tex> в состояние <tex>(q_2,a_2,X_2)</tex> как <tex>(q_1,a_1,X_1)\vdash(q_2,a_2,X_2)</tex>. Переход автомата из состояния <tex>(q_1,a_1,X_1)</tex> в состояние <tex>(q_{p+1},a_{p+1},X_{p+1})</tex> через <tex>P</tex> промежуточных состояний обозначаем <tex>(q_1,a_1,X_1)\vdash^*_P(q_{p+1},a_{p+1},X_{p+1})</tex>.

==Пример==
Автомат <tex>P=(\{q,p\},\{0,1\},\{Z_0,X\},\delta,q,Z_0,\{p\})</tex> с функией перехода <tex>\delta</tex>:
# <tex>\delta(q,0,Z_0)=(q,XZ_0)</tex>
# <tex>\delta(q,0,X)=(q,XX)</tex>
# <tex>\delta(q,1,X)=(q,X)</tex>
# <tex>\delta(q,0,Z_0)=(p,Z_0)</tex>
# <tex>\delta(p,0,Z_0)=(p,XZ_0)</tex>
# <tex>\delta(p,0,X)=(p,XX)</tex>
# <tex>\delta(p,1,X)=(p,X)</tex>
[[Файл:МП-автомат.png]]

Алгоритм Эрли

2011-01-15T21:48:55Z

Smetannikov.Ivan: /* Алгоритм Эрли */

{{Определение
|definition =
Пусть <tex>G = (N, \Sigma, P, S)</tex> {{---}} контекстно свободная грамматика и <tex>\omega = a_1 a_2 ... a_n</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
Объект вида <tex>[A \rightarrow X_1 X_2 ... X_k \cdot X_{k+1} ... X_m, i]</tex> назовем ситуацией, относящейся к цепочке <tex>\omega</tex>, если <tex>A \rightarrow X_1 ... X_m </tex> {{---}} правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex>. <tex>\cdot</tex> является метасимволом, не принадлежащим ни <tex>N</tex>, ни <tex>\Sigma</tex>. <tex>k \in \mathbb{N}, 0 \leqslant k \leqslant m</tex>.
}}

{{Определение
|definition =
Для каждого <tex>0 \leqslant j \leqslant n</tex> построим список ситуаций <tex>I_j</tex> такой, что <tex>[A \rightarrow \alpha \cdot \beta , i] \in I_j</tex> для <tex>0 \leqslant j \leqslant n</tex> тогда и только тогда, когда для некоторых <tex>\gamma</tex> и <tex>\delta</tex> существуют выводы <tex>S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i</tex> и <tex>\alpha \Rightarrow^* a_{i+1} ... a_j</tex>.
}}

{{Определение
|definition =
Последовательность списков <tex>I_0, I_1, ..., I_n</tex> называется списком разбора для входной цепочки <tex>\omega</tex>.
}}

==Алгоритм Эрли==

Вход. контекстно свободная грамматика <tex>G = (N, \Sigma, P, S)</tex> и входная цепочка <tex>\omega = a_1 a_2 ... a_n</tex>. 
Выход. Список разбора <tex>I_0, I_1, ... I_n</tex> для цепочки <tex>\omega</tex>. 
Метод. 
Строим <tex>I_0</tex> 
Шаг 1. Если <tex>S \rightarrow \alpha</tex> {{---}} правило из <tex>P</tex>, включить <tex>[S \rightarrow \cdot \alpha, 0]</tex> в <tex>I_0</tex>. 
Выполняем шаги 2 и 3 до тех пор, пока можем включать новые ситуации в <tex>I_0</tex>. 
Шаг 2. Если <tex>[B \rightarrow \gamma \cdot, 0] \in I_0</tex>, включить в <tex>I_0</tex> ситуацию <tex>[A \rightarrow \alpha B \cdot \beta, 0]</tex> для всех <tex>[A \rightarrow \alpha \cdot B \beta, 0]</tex>, уже принадлежащих <tex>I_0</tex>. 
Шаг 3. Допустим, что <tex>[A \rightarrow \alpha \cdot B \beta, 0] \in I_0</tex>. Для каждого правила из <tex>P</tex> вида <tex>B \rightarrow \gamma</tex> включить в <tex>I_0</tex> ситуацию <tex>[B \rightarrow \cdot \gamma, 0]</tex> (если она еще не там). 
Построение <tex>I_j</tex> по <tex>I_0, I_1, ..., I_{j-1}</tex>. 
Шаг 4. Для каждой ситуации <tex>[B \rightarrow \alpha \cdot a \beta, i] \in I_{j-1}</tex>, для которой <tex>a = a_j</tex> включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \alpha a \cdot \beta, i] </tex>. 
Выполняем шаги 5 и 6 до тех пор, пока можем включать новые ситуации в <tex>I_j</tex>. 
Шаг 5. Пусть <tex>[A \rightarrow \alpha \cdot , i] \in I_j</tex>. Ищем ситуации вида <tex>[B \rightarrow \gamma \cdot A \delta, k]</tex>. Для каждой из них включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \gamma A \cdot \delta, k]</tex>. 
Шаг 6. Пусть <tex>[A \rightarrow \alpha \cdot B \beta, i] \in I_j</tex>. Для каждого <tex>B \rightarrow \gamma</tex> из <tex>P</tex> включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \cdot \gamma, j]</tex>. 
Вычисляем все <tex>I_j</tex> для <tex>0 \leqslant j \leqslant n</tex>. 
<tex>\omega \in L(G) \Leftrightarrow [S \rightarrow \alpha \cdot, 0] \in I_n</tex>. 
                               '''Шаг 4.'''                                                       '''Шаг 5.'''                                                  '''Шаг 6.''' 
[[Файл:Эрли2.png]] [[Файл:Эрли1.png]] [[Файл:Эрли3.png]]

==Литература==
*А.Ахо, Дж. Ульман. Теория синтакического анализа, перевода и компиляции. Том 1. Синтактический анализ.

Детерминированные автоматы с магазинной памятью

2011-01-15T21:42:31Z

Smetannikov.Ivan:

{{Определение
|definition =
Определим <tex>P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)</tex> как детерминированный автомат с магазинной (стековой) памятью, где 
* <tex>Q</tex>: конечное множество состояний.
* <tex>\Sigma</tex>: конечное множество входных символов.
* <tex>\Gamma</tex>: конечный магазинный алфавит {{---}} множество символов, которые можно помещать в магазин.
* <tex>\delta</tex>: функция переходов. <tex>\delta (q,a,X)=(p,\gamma)</tex>, где для кадой тройки <tex>(q,a,X)</tex> пара <tex>(p,\gamma)</tex> задана единственным образом, где
** <tex>q</tex>: текущее состояние из Q.
** <tex>a</tex>: входной символ.
** <tex>X</tex>: магазинный символ из <tex>\Gamma</tex>.
** <tex>p</tex>: новое состояние из Q.
** <tex>\gamma</tex>: цепочка магазинных символов, замещающих <tex>X</tex> на вершине магазина.
* <tex>q_0</tex>: начальное состояние.
* <tex>Z_0</tex>: начальный магазинный символ (маркер дна). Находится в магазине в начале работы автомата.
* <tex>F</tex>: множество допускающих состояний.
}}

Будем обозначать переход автомата из состояния <tex>(q_1,a_1,X_1)</tex> в состояние <tex>(q_2,a_2,X_2)</tex> как <tex>(q_1,a_1,X_1)\vdash(q_2,a_2,X_2)</tex>. Переход автомата из состояния <tex>(q_1,a_1,X_1)</tex> в состояние <tex>(q_{p+1},a_{p+1},X_{p+1})</tex> через <tex>P</tex> промежуточных состояний обозначаем <tex>(q_1,a_1,X_1)\vdash^*_P(q_{p+1},a_{p+1},X_{p+1})</tex>.

==Пример==
Автомат <tex>P=(\{q,p\},\{0,1\},\{Z_0,X\},\delta,q,Z_0,\{p\})</tex> с функией перехода <tex>\delta</tex>:
# <tex>\delta(q,0,Z_0)=(q,XZ_0)</tex>
# <tex>\delta(q,0,X)=(q,XX)</tex>
# <tex>\delta(q,1,X)=(q,X)</tex>
# <tex>\delta(q,0,Z_0)=(p,Z_0)</tex>
# <tex>\delta(p,0,Z_0)=(p,XZ_0)</tex>
# <tex>\delta(p,0,X)=(p,XX)</tex>
# <tex>\delta(p,1,X)=(p,X)</tex>
[[Файл:МП-автомат.png]]

Алгоритм Эрли

2011-01-15T21:37:23Z

Smetannikov.Ivan:

{{Определение
|definition =
Пусть <tex>G = (N, \Sigma, P, S)</tex> {{---}} контекстно свободная грамматика и <tex>\omega = a_1 a_2 ... a_n</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
Объект вида <tex>[A \rightarrow X_1 X_2 ... X_k \cdot X_{k+1} ... X_m, i]</tex> назовем ситуацией, относящейся к цепочке <tex>\omega</tex>, если <tex>A \rightarrow X_1 ... X_m </tex> {{---}} правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex>. <tex>\cdot</tex> является метасимволом, не принадлежащим ни <tex>N</tex>, ни <tex>\Sigma</tex>. <tex>k \in \mathbb{N}, 0 \leqslant k \leqslant m</tex>.
}}

{{Определение
|definition =
Для каждого <tex>0 \leqslant j \leqslant n</tex> построим список ситуаций <tex>I_j</tex> такой, что <tex>[A \rightarrow \alpha \cdot \beta , i] \in I_j</tex> для <tex>0 \leqslant j \leqslant n</tex> тогда и только тогда, когда для некоторых <tex>\gamma</tex> и <tex>\delta</tex> существуют выводы <tex>S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i</tex> и <tex>\alpha \Rightarrow^* a_{i+1} ... a_j</tex>.
}}

{{Определение
|definition =
Последовательность списков <tex>I_0, I_1, ..., I_n</tex> называется списком разбора для входной цепочки <tex>\omega</tex>.
}}

==Алгоритм Эрли==

Вход. контекстно свободная грамматика <tex>G = (N, \Sigma, P, S)</tex> и входная цепочка <tex>\omega = a_1 a_2 ... a_n</tex>. 
Выход. Список разбора <tex>I_0, I_1, ... I_n</tex> для цепочки <tex>\omega</tex>. 
Метод. 
Строим <tex>I_0</tex> 
Шаг 1. Если <tex>S \rightarrow \alpha</tex> {{---}} правило из <tex>P</tex>, включить <tex>[S \rightarrow \cdot \alpha, 0]</tex> в <tex>I_0</tex>. 
Выполняем шаги 2 и 3 до тех пор, пока можем включать новые ситуации в <tex>I_0</tex>. 
Шаг 2. Если <tex>[B \rightarrow \gamma \cdot, 0] \in I_0</tex>, включить в <tex>I_0</tex> ситуацию <tex>[A \rightarrow \alpha B \cdot \beta, 0]</tex> для всех <tex>[A \rightarrow \alpha \cdot B \beta, 0]</tex>, уже принадлежащих <tex>I_0</tex>. 
Шаг 3. Допустим, что <tex>[A \rightarrow \alpha \cdot B \beta, 0] \in I_0</tex>. Для каждого правила из <tex>P</tex> вида <tex>B \rightarrow \gamma</tex> включить в <tex>I_0</tex> ситуацию <tex>[B \rightarrow \cdot \gamma, 0]</tex> (если она еще не там). 
Построение <tex>I_j</tex> по <tex>I_0, I_1, ..., I_{j-1}</tex>. 
Шаг 4. Для каждой ситуации <tex>[B \rightarrow \alpha \cdot a \beta, i] \in I_{j-1}</tex>, для которой <tex>a = a_j</tex> включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \alpha a \cdot \beta, i] </tex>. 
Выполняем шаги 5 и 6 до тех пор, пока можем включать новые ситуации в <tex>I_j</tex>. 
Шаг 5. Пусть <tex>[A \rightarrow \alpha \cdot , i] \in I_j</tex>. Ищем ситуации вида <tex>[B \rightarrow \alpha \cdot A \beta, k]</tex>. Для каждой из них включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \alpha A \cdot \beta, k]</tex>. 
Шаг 6. Пусть <tex>[A \rightarrow \alpha \cdot B \beta, i] \in I_j</tex>. Для каждого <tex>B \rightarrow \gamma</tex> из <tex>P</tex> включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \cdot \gamma, j]</tex>. 
Вычисляем все <tex>I_j</tex> для <tex>0 \leqslant j \leqslant n</tex>. 
<tex>\omega \in L(G) \Leftrightarrow [S \rightarrow \alpha \cdot, 0] \in I_n</tex>. 
                               '''Шаг 4.'''                                                       '''Шаг 5.'''                                                  '''Шаг 6.''' 
[[Файл:Эрли2.png]] [[Файл:Эрли1.png]] [[Файл:Эрли3.png]]

==Литература==
*А.Ахо, Дж. Ульман. Теория синтакического анализа, перевода и компиляции. Том 1. Синтактический анализ.

Файл:Эрли3.png

2011-01-15T21:32:38Z

Smetannikov.Ivan:

Файл:Эрли2.png

2011-01-15T21:31:12Z

Smetannikov.Ivan:

Файл:Эрли1.png

2011-01-15T21:28:47Z

Smetannikov.Ivan:

Алгоритм Эрли

2011-01-15T19:23:06Z

Smetannikov.Ivan:

{{Определение
|definition =
Пусть <tex>G = (N, \Sigma, P, S)</tex> {{---}} контекстно свободная грамматика и <tex>\omega = a_1 a_2 ... a_n</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
Объект вида <tex>[A \rightarrow X_1 X_2 ... X_k \cdot X_{k+1} ... X_m, i]</tex> назовем ситуацией, относящейся к цепочке <tex>\omega</tex>, если <tex>A \rightarrow X_1 ... X_m </tex> {{---}} правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex>. <tex>\cdot</tex> является метасимволом, не принадлежащим ни <tex>N</tex>, ни <tex>\Sigma</tex>. <tex>k \in \mathbb{N}, 0 \leqslant k \leqslant m</tex>.
}}

{{Определение
|definition =
Для каждого <tex>0 \leqslant j \leqslant n</tex> построим список ситуаций <tex>I_j</tex> такой, что <tex>[A \rightarrow \alpha \cdot \beta , i] \in I_j</tex> для <tex>0 \leqslant j \leqslant n</tex> тогда и только тогда, когда для некоторых <tex>\gamma</tex> и <tex>\delta</tex> существуют выводы <tex>S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i</tex> и <tex>\alpha \Rightarrow^* a_{i+1} ... a_j</tex>.
}}

{{Определение
|definition =
Последовательность списков <tex>I_0, I_1, ..., I_n</tex> называется списком разбора для входной цепочки <tex>\omega</tex>.
}}

==Алгоритм Эрли==

Вход. контекстно свободная грамматика <tex>G = (N, \Sigma, P, S)</tex> и входная цепочка <tex>\omega = a_1 a_2 ... a_n</tex>. 
Выход. Список разбора <tex>I_0, I_1, ... I_n</tex> для цепочки <tex>\omega</tex>. 
Метод. 
Строим <tex>I_0</tex> 
Шаг 1. Если <tex>S \rightarrow \alpha</tex> {{---}} правило из <tex>P</tex>, включить <tex>[S \rightarrow \cdot \alpha, 0]</tex> в <tex>I_0</tex>. 
Выполняем шаги 2 и 3 до тех пор, пока можем включать новые ситуации в <tex>I_0</tex>. 
Шаг 2. Если <tex>[B \rightarrow \gamma \cdot, 0] \in I_0</tex>, включить в <tex>I_0</tex> ситуацию <tex>[A \rightarrow \alpha B \cdot \beta, 0]</tex> для всех <tex>[A \rightarrow \alpha \cdot B \beta, 0]</tex>, уже принадлежащих <tex>I_0</tex>. 
Шаг 3. Допустим, что <tex>[A \rightarrow \alpha \cdot B \beta, 0] \in I_0</tex>. Для каждого правила из <tex>P</tex> вида <tex>B \rightarrow \gamma</tex> включить в <tex>I_0</tex> ситуацию <tex>[B \rightarrow \cdot \gamma, 0]</tex> (если она еще не там). 
Построение <tex>I_j</tex> по <tex>I_0, I_1, ..., I_{j-1}</tex>. 
Шаг 4. Для каждой ситуации <tex>[B \rightarrow \alpha \cdot a \beta, i] \in I_{j-1}</tex>, для которой <tex>a = a_j</tex> включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \alpha a \cdot \beta, i] </tex>. 
Выполняем шаги 5 и 6 до тех пор, пока можем включать новые ситуации в <tex>I_j</tex>. 
Шаг 5. Пусть <tex>[A \rightarrow \alpha \cdot , i] \in I_j</tex>. Ищем ситуации вида <tex>[B \rightarrow \alpha \cdot A \beta, k]</tex>. Для каждой из них включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \alpha A \cdot \beta, k]</tex>. 
Шаг 6. Пусть <tex>[A \rightarrow \alpha \cdot B \beta, i] \in I_j</tex>. Для каждого <tex>B \rightarrow \gamma</tex> из <tex>P</tex> включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \cdot \gamma, j]</tex>. 
Вычисляем все <tex>I_j</tex> для <tex>0 \leqslant j \leqslant n</tex>. 
<tex>\omega \in L(G) \Leftrightarrow [S \rightarrow \alpha \cdot, 0] \in I_n</tex>.

==Литература==
*А.Ахо, Дж. Ульман. Теория синтакического анализа, перевода и компиляции. Том 1. Синтактический анализ.

Детерминированные автоматы с магазинной памятью

2011-01-15T03:41:08Z

Smetannikov.Ivan:

{{Определение
|definition =
Определим <tex>P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)</tex> как детерминированный автомат с магазинной (стековой) памятью, где 
* <tex>Q</tex>: конечное множество состояний.
* <tex>\Sigma</tex>: конечное множество входных символов.
* <tex>\Gamma</tex>: конечный магазинный алфавит {{---}} множество символов, которые можно помещать в магазин.
* <tex>\delta</tex>: функция переходов. <tex>\delta (q,a,X)=(p,\gamma)</tex>, где
** <tex>q</tex>: текущее состояние из Q.
** <tex>a</tex>: входной символ.
** <tex>X</tex>: магазинный символ из <tex>\Gamma</tex>.
** <tex>p</tex>: новое состояние из Q.
** <tex>\gamma</tex>: цепочка магазинных символов, замещающих <tex>X</tex> на вершине магазина.
* <tex>q_0</tex>: начальное состояние.
* <tex>Z_0</tex>: начальный магазинный символ (маркер дна). Находится в магазине в начале работы автомата.
* <tex>F</tex>: множество допускающих состояний.
}}

Будем обозначать переход автомата из состояния <tex>(q_1,a_1,X_1)</tex> в состояние <tex>(q_2,a_2,X_2)</tex> как <tex>(q_1,a_1,X_1)\vdash(q_2,a_2,X_2)</tex>. Переход автомата из состояния <tex>(q_1,a_1,X_1)</tex> в состояние <tex>(q_{p+1},a_{p+1},X_{p+1})</tex> через <tex>P</tex> промежуточных состояний обозначаем <tex>(q_1,a_1,X_1)\vdash^*_P(q_{p+1},a_{p+1},X_{p+1})</tex>.

==Пример==
Автомат <tex>P=(\{q,p\},\{0,1\},\{Z_0,X\},\delta,q,Z_0,\{p\})</tex> с функией перехода <tex>\delta</tex>:
# <tex>\delta(q,0,Z_0)=(q,XZ_0)</tex>
# <tex>\delta(q,0,X)=(q,XX)</tex>
# <tex>\delta(q,1,X)=(q,X)</tex>
# <tex>\delta(q,0,Z_0)=(p,Z_0)</tex>
# <tex>\delta(p,0,Z_0)=(p,XZ_0)</tex>
# <tex>\delta(p,0,X)=(p,XX)</tex>
# <tex>\delta(p,1,X)=(p,X)</tex>
[[Файл:МП-автомат.png]]

Файл:МП-автомат.png

2011-01-15T03:39:52Z

Smetannikov.Ivan:

Детерминированные автоматы с магазинной памятью

2011-01-15T02:48:46Z

Smetannikov.Ivan: Новая страница: «{{Определение |definition = Определим <tex>P=(Q,\Sigma,\Gamma,\delta,q_0,Z_0,F)</tex> как детерминированный автомат…»

Алгоритм Эрли

2011-01-14T23:22:05Z

Smetannikov.Ivan:

{{Определение
|definition =
Пусть <tex>G = (N, \Sigma, P, S)</tex> {{---}} контекстно свободная грамматика и <tex>\omega = a_1 a_2 ... a_n</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
Объект вида <tex>[A \rightarrow X_1 X_2 ... X_k \cdot X_{k+1} ... X_m, i]</tex> назовем ситуацией, относящейся к цепочке <tex>\omega</tex>, если <tex>A \rightarrow X_1 ... X_m </tex> {{---}} правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex>. <tex>\cdot</tex> является метасимволом, не принадлежащим ни <tex>N</tex>, ни <tex>\Sigma</tex>. <tex>k \in \mathbb{N}, 0 \leqslant k \leqslant m</tex>.
}}

{{Определение
|definition =
Для каждого <tex>0 \leqslant j \leqslant n</tex> построим список ситуаций <tex>I_j</tex> такой, что <tex>[A \rightarrow \alpha \beta \cdot , i] \in I_j</tex> для <tex>0 \leqslant j \leqslant n</tex> тогда и только тогда, когда для некоторых <tex>\gamma</tex> и <tex>\delta</tex> существуют выводы <tex>S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i</tex> и <tex>\alpha \Rightarrow^* a_{i+1} ... a_j</tex>.
}}

{{Определение
|definition =
Последовательность списков <tex>I_0, I_1, ..., I_n</tex> называется списком разбора для входной цепочки <tex>\omega</tex>.
}}

==Алгоритм Эрли==

Вход. контекстно свободная грамматика <tex>G = (N, \Sigma, P, S)</tex> и входная цепочка <tex>\omega = a_1 a_2 ... a_n</tex>. 
Выход. Список разбора <tex>I_0, I_1, ... I_n</tex> для цепочки <tex>\omega</tex>. 
Метод. 
Строим <tex>I_0</tex> 
Шаг 1. Если <tex>S \rightarrow \alpha</tex> {{---}} правило из <tex>P</tex>, включить <tex>[S \rightarrow \cdot \alpha, 0]</tex> в <tex>I_0</tex>. 
Выполняем шаги 2 и 3 до тех пор, пока можем включать новые ситуации в <tex>I_0</tex>. 
Шаг 2. Если <tex>[B \rightarrow \gamma \cdot, 0] \in I_0</tex>, включить в <tex>I_0</tex> ситуацию <tex>[A \rightarrow \alpha B \cdot \beta, 0]</tex> для всех <tex>[A \rightarrow \alpha \cdot B \beta, 0]</tex>, уже принадлежащих <tex>I_0</tex>. 
Шаг 3. Допустим, что <tex>[A \rightarrow \alpha \cdot B \beta, 0] \in I_0</tex>. Для каждого правила из <tex>P</tex> вида <tex>B \rightarrow \gamma</tex> включить в <tex>I_0</tex> ситуацию <tex>[B \rightarrow \cdot \gamma, 0]</tex> (если она еще не там). 
Построение <tex>I_j</tex> по <tex>I_0, I_1, ..., I_{j-1}</tex>. 
Шаг 4. Для каждой ситуации <tex>[B \rightarrow \alpha \cdot a \beta, i] \in I_{j-1}</tex>, для которой <tex>a = a_j</tex> включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \alpha a \cdot \beta, i] </tex>. 
Выполняем шаги 5 и 6 до тех пор, пока можем включать новые ситуации в <tex>I_j</tex>. 
Шаг 5. Пусть <tex>[A \rightarrow \alpha \cdot , i] \in I_j</tex>. Ищем ситуации вида <tex>[B \rightarrow \alpha \cdot A \beta, k]</tex>. Для каждой из них включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \alpha A \cdot \beta, k]</tex>. 
Шаг 6. Пусть <tex>[A \rightarrow \alpha \cdot B \beta, i] \in I_j</tex>. Для каждого <tex>B \rightarrow \gamma</tex> из <tex>P</tex> включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \cdot \gamma, j]</tex>. 
Вычисляем все <tex>I_j</tex> для <tex>0 \leqslant j \leqslant n</tex>. 
<tex>\omega \in L(G) \Leftrightarrow [S \rightarrow \alpha \cdot, 0] \in I_n</tex>.

==Литература==
*А.Ахо, Дж. Ульман. Теория синтакического анализа, перевода и компиляции. Том 1. Синтактический анализ.

Алгоритм Эрли

2011-01-14T23:18:03Z

Smetannikov.Ivan:

{{Определение
|definition =
Пусть <tex>G = (N, \Sigma, P, S)</tex> {{---}} контекстно свободная грамматика и <tex>\omega = a_1 a_2 ... a_n</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
Объект вида <tex>[A \rightarrow X_1 X_2 ... X_k \cdot X_{k+1} ... X_m, i]</tex> назовем ситуацией, относящейся к цепочке <tex>\omega</tex>, если <tex>A \rightarrow X_1 ... X_m </tex> {{---}} правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex>. <tex>\cdot</tex> является метасимволом, не принадлежащим ни <tex>N</tex>, ни <tex>\Sigma</tex>. <tex>k \in \mathbb{N}, 0 \leqslant k \leqslant m</tex>.
}}

{{Определение
|definition =
Для каждого <tex>0 \leqslant j \leqslant n</tex> построим список ситуаций <tex>I_j</tex> такой, что <tex>[A \rightarrow \alpha \beta \cdot , i] \in I_j</tex> для <tex>0 \leqslant j \leqslant n</tex> тогда и только тогда, когда для некоторых <tex>\gamma</tex> и <tex>\delta</tex> существуют выводы <tex>S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i</tex> и <tex>\alpha \Rightarrow^* a_{i+1} ... a_j</tex>.
}}

{{Определение
|definition =
Последовательность списков <tex>I_0, I_1, ..., I_n</tex> называется списком разбора для входной цепочки <tex>\omega</tex>.
}}

==Алгоритм Эрли==

Вход. контекстно свободная грамматика <tex>G = (N, \Sigma, P, S)</tex> и входная цепочка <tex>\omega = a_1 a_2 ... a_n</tex>. 
Выход. Список разбора <tex>I_0, I_1, ... I_n</tex> для цепочки <tex>\omega</tex>. 
Метод. 
Строим <tex>I_0</tex> 
Шаг 1. Если <tex>S \rightarrow \alpha</tex> {{---}} правило из <tex>P</tex>, включить <tex>[S \rightarrow \cdot \alpha, 0]</tex> в <tex>I_0</tex>. 
Выполняем шаги 2 и 3 до тех пор, пока можем включать новые ситуации в <tex>I_0</tex>. 
Шаг 2. Если <tex>[B \rightarrow \gamma \cdot, 0] \in I_0</tex>, включить в <tex>I_0</tex> ситуацию <tex>[A \rightarrow \alpha B \cdot \beta, 0]</tex> для всех <tex>[A \rightarrow \alpha \cdot B \beta, 0]</tex>, уже принадлежащих <tex>I_0</tex>. 
Шаг 3. Допустим, что <tex>[A \rightarrow \alpha \cdot B \beta, 0] \in I_0</tex>. Для каждого правила из <tex>P</tex> вида <tex>B \rightarrow \gamma</tex> включить в <tex>I_0</tex> ситуацию <tex>[B \rightarrow \cdot \gamma, 0]</tex> (если она еще не там). 
Построение <tex>I_j</tex> по <tex>I_0, I_1, ..., I_{j-1}</tex>. 
Шаг 4. Для каждой ситуации <tex>[B \rightarrow \alpha \cdot a \beta, i] \in I_{j-1}</tex>, для которой <tex>a = a_j</tex> включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \alpha a \cdot \beta, i] </tex>. 
Выполняем шаги 5 и 6 до тех пор, пока можем включать новые ситуации в <tex>I_j</tex>. 
Шаг 5. Пусть <tex>[A \rightarrow \alpha \cdot , i] \in I_j</tex>. Ищем ситуации вида <tex>[B \rightarrow \alpha \cdot A \beta, k]</tex>. Для каждой из них включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \alpha A \cdot \beta, k]</tex>. 
Шаг 6. Пусть <tex>[A \rightarrow \alpha \cdot B \beta, i] \in I_j</tex>. Для каждого <tex>B \rightarrow \gamma</tex> из <tex>P</tex> включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \cdot \gamma, j]</tex>. 
Вычисляем все <tex>I_j</tex> для <tex>0 \leqslant j \leqslant n</tex>. 
<tex>\omega \in L(G) \Leftrightarrow [S \rightarrow \alpha \cdot, 0] \in I_n</tex>.

Алгоритм Эрли

2011-01-14T22:57:43Z

Smetannikov.Ivan:

{{Определение
|definition =
Пусть <tex>G = (N, \Sigma, P, S)</tex> {{---}} контекстно свободная грамматика и <tex>\omega = a_1 a_2 ... a_n</tex> {{---}} входная цепочка из <tex>\Sigma^*</tex>.
Объект вида <tex>[A \rightarrow X_1 X_2 ... X_k \cdot X_{k+1} ... X_m, i]</tex> назовем ситуацией, относящейся к цепочке <tex>\omega</tex>, если <tex>A \rightarrow X_1 ... X_m </tex> {{---}} правило из <tex>P</tex> и <tex>0 \leqslant i \leqslant n</tex>. <tex>\cdot</tex> является метасимволом, не принадлежащим ни <tex>N</tex>, ни <tex>\Sigma</tex>. <tex>k \in \mathbb{N}, 0 \leqslant k \leqslant m</tex>.
}}

{{Определение
|definition =
Для каждого <tex>0 \leqslant j \leqslant n</tex> построим список ситуаций <tex>I_j</tex> такой, что <tex>[A \rightarrow \alpha \beta \cdot , i] \in I_j</tex> для <tex>0 \leqslant j \leqslant n</tex> тогда и только тогда, когда для некоторых <tex>\gamma</tex> и <tex>\delta</tex> существуют выводы <tex>S \Rightarrow^* \gamma A \delta, \gamma \Rightarrow^* a_1...a_i</tex> и <tex>\alpha \Rightarrow^* a_{i+1} ... a_j</tex>.
}}

{{Определение
|definition =
Последовательность списков <tex>I_0, I_1, ..., I_n</tex> называется списком разбора для входной цепочки <tex>\omega</tex>.
}}

==Алгоритм Эрли==

Вход. контекстно свободная грамматика <tex>G = (N, \Sigma, P, S)</tex> и входная цепочка <tex>\omega = a_1 a_2 ... a_n</tex>. 
Выход. Список разбора <tex>I_0, I_1, ... I_n</tex> для цепочки <tex>\omega</tex>. 
Метод. 
Строим <tex>I_0</tex> 
Шаг 1. Если <tex>S \rightarrow \alpha</tex> {{---}} правило из <tex>P</tex>, включить <tex>[S \rightarrow \cdot \alpha, 0]</tex> в <tex>I_0</tex>. 
Выполняем шаги 2 и 3 до тех пор, пока можем включать новые ситуации в <tex>I_0</tex>. 
Шаг 2. Если <tex>[B \rightarrow \gamma \cdot, 0] \in I_0</tex>, включить в <tex>I_0</tex> ситуацию <tex>[A \rightarrow \alpha B \cdot \beta, 0]</tex> для всех <tex>[A \rightarrow \alpha \cdot B \beta, 0]</tex>, уже принадлежащих <tex>I_0</tex>. 
Шаг 3. Допустим, что <tex>[A \rightarrow \alpha \cdot B \beta, 0] \in I_0</tex>. Для каждого правила из <tex>P</tex> вида <tex>B \rightarrow \gamma</tex> включить в <tex>I_0</tex> ситуацию <tex>[B \rightarrow \cdot \gamma, 0]</tex> (если она еще не там). 
Построение <tex>I_j</tex> по <tex>I_0, I_1, ..., I_{j-1}</tex>. 
Шаг 4. Для каждой ситуации <tex>[B \rightarrow \alpha \cdot a \beta, i] \in I_{j-1}</tex>, для которой <tex>a = a_j</tex> включить в <tex>I_j</tex> ситуацию <tex>[B \rightarrow \alpha a \cdot \beta, i] </tex>. 
Выполняем шаги 5 и 6 до тех пор, пока можем включать новые ситуации в <tex>I_j</tex>.

Алгоритм Эрли

2011-01-14T22:38:54Z

Smetannikov.Ivan:

Алгоритм Эрли

2011-01-14T22:09:02Z

Smetannikov.Ivan: Новая страница: «{{Определение |definition = Пусть <tex>G = (N, \Sigma, P, S)</tex> {{---}} контекстно свободная грамматика и <tex>\omeg…»

Евклидовы кольца

2010-10-14T01:04:47Z

Smetannikov.Ivan: /* Свойства */

{{Определение
|definition=
Евклидово кольцо - [[Определение кольца, подкольца, изоморфизмы колец|кольцо]], в котором существует алгоритм евклида.
}}
{{Определение
|definition=
Евклидово кольцо - это [[Делители нуля, области целостности|область целостности]] <tex>R</tex>, для которой определена евклидова норма <tex>\|\cdot \| :R \rightarrow \mathbb{N}\cup\{-\infty\}</tex>, причем <tex>\|a\|=-\infty \Leftrightarrow a=0</tex>, для <tex>\forall a,b\in R \exists</tex> представление <tex>a=b\cdot q + r, для которого \|r\|<\|d\|</tex>
}}
==Примеры==
#<tex>\mathbb{Z}</tex>, тогда <tex>\|a\|=|a|</tex>
#<tex>\mathbb{Q}[x]</tex>, тогда <tex>\|f(x)\|=deg(f(x))</tex> 
<tex>|a\cdot b|^2=|a|^2\cdot |b|^2\geq |b|^2</tex>, кроме того <tex>\|a\cdot b\|\geq \|b\|=|b|^2 \Rightarrow |a\cdot b|^2=\|a\cdot b\|</tex>
#<tex>\mathbb{Z}[i]: \|a+b\cdot i\|=a^2+b^2</tex>, т.e. <tex>\|z\|=|z|^2</tex>

==Алгоритм Евклида==
Изначально даны <tex>a,b\in R</tex>, необходимо найти их НОД. Пусть <tex>a<b</tex>. Поделим <tex>b</tex> на <tex>a</tex> с остатком 
<tex>b=a\cdot u_1 + r_1 (0\le r_1<a)</tex>, 
<tex>a=r_1\cdot u_2 + r_2 (0\le r_2<r_1)</tex>, 
........................... 
<tex>r_{n-1}=r_n\cdot u_{n+1} + r_{n+1} (0\le r_{n+1}<r_n)</tex>, 
<tex>r_n=r_{n+1}\cdot u_{n+2}</tex>. 
Число <tex>r_{n+1}</tex> является НОД чисел <tex>a</tex> и <tex>b</tex>. Алгоритм заканчивает свою работу, поскольку <tex>\forall a \in \mathbb{N} \cup \{-\infty\}</tex> может строго превосходить лишь конечное количество других таких чисел.

==Свойства==
#В евклидовых кольцах единственно разложение на множители.
#<tex>a\cdot b\vdots p \Rightarrow a\vdots p \lor b\vdots p</tex> Пусть <tex>gcd(a,p)=1 \Rightarrow 1=a\cdot x+p\cdot y; x,y \in \mathbb{R} \Rightarrow b=a\cdot b\cdot x + p\cdot b\cdot y \vdots p \Rightarrow b\vdots p</tex>
#Если а и b - не [[Единицы (обратимые элементы), группа обратимых элементов|обратимы]], то <tex>\|a\cdot b\|>\|b\|</tex> Пусть <tex>b=k\cdot a\cdot b+r;r\neq 0;\|r\|<\|a\cdot b\|\Rightarrow r=b-k\cdot a\cdot b\Rightarrow \|r\|=\|b\cdot(1-k\cdot a)\|>\|b\|</tex>

Евклидовы кольца

2010-10-14T00:29:31Z

Smetannikov.Ivan:

{{Определение
|definition=
Евклидово кольцо - [[Определение кольца, подкольца, изоморфизмы колец|кольцо]], в котором существует алгоритм евклида.
}}
{{Определение
|definition=
Евклидово кольцо - это [[Делители нуля, области целостности|область целостности]] <tex>R</tex>, для которой определена евклидова норма <tex>\|\cdot \| :R \rightarrow \mathbb{N}\cup\{-\infty\}</tex>, причем <tex>\|a\|=-\infty \Leftrightarrow a=0</tex>, для <tex>\forall a,b\in R \exists</tex> представление <tex>a=b\cdot q + r, для которого \|r\|<\|d\|</tex>
}}
==Примеры==
#<tex>\mathbb{Z}</tex>, тогда <tex>\|a\|=|a|</tex>
#<tex>\mathbb{Q}[x]</tex>, тогда <tex>\|f(x)\|=deg(f(x))</tex> 
<tex>|a\cdot b|^2=|a|^2\cdot |b|^2\geq |b|^2</tex>, кроме того <tex>\|a\cdot b\|\geq \|b\|=|b|^2 \Rightarrow |a\cdot b|^2=\|a\cdot b\|</tex>
#<tex>\mathbb{Z}[i]: \|a+b\cdot i\|=a^2+b^2</tex>, т.e. <tex>\|z\|=|z|^2</tex>

==Алгоритм Евклида==
Изначально даны <tex>a,b\in R</tex>, необходимо найти их НОД. Пусть <tex>a<b</tex>. Поделим <tex>b</tex> на <tex>a</tex> с остатком 
<tex>b=a\cdot u_1 + r_1 (0\le r_1<a)</tex>, 
<tex>a=r_1\cdot u_2 + r_2 (0\le r_2<r_1)</tex>, 
........................... 
<tex>r_{n-1}=r_n\cdot u_{n+1} + r_{n+1} (0\le r_{n+1}<r_n)</tex>, 
<tex>r_n=r_{n+1}\cdot u_{n+2}</tex>. 
Число <tex>r_{n+1}</tex> является НОД чисел <tex>a</tex> и <tex>b</tex>. Алгоритм заканчивает свою работу, поскольку <tex>\forall a \in \mathbb{N} \cup \{-\infty\}</tex> может строго превосходить лишь конечное количество других таких чисел.

==Свойства==
#В евклидовых кольцах единственно разложение на множители.
#<tex>a\cdot b\vdots p \Rightarrow a\vdots p \lor b\vdots p</tex> 
Пусть <tex>gcd(a,p)=1 \Rightarrow 1=a\cdot x+p\cdot y; x,y \in \mathbb{R} \Rightarrow b=a\cdot b\cdot x + p\cdot b\cdot y \vdots p \Rightarrow b\vdots p</tex>

Евклидовы кольца

2010-10-14T00:07:50Z

Smetannikov.Ivan: /* Примеры */

{{Определение
|definition=
Евклидово кольцо - [[Определение кольца, подкольца, изоморфизмы колец|кольцо]], в котором существует алгоритм евклида.
}}
{{Определение
|definition=
Евклидово кольцо - это [[Делители нуля, области целостности|область целостности]] <tex>R</tex>, для которой определена евклидова норма <tex>\|\cdot \| :R \rightarrow \mathbb{N}\cup\{-\infty\}</tex>, причем <tex>\|a\|=-\infty \Leftrightarrow a=0</tex>, для <tex>\forall a,b\in R \exists</tex> представление <tex>a=b\cdot q + r, для которого \|r\|<\|d\|</tex>
}}
==Примеры==
#<tex>\mathbb{Z}</tex>, тогда <tex>\|a\|=|a|</tex>
#<tex>\mathbb{Q}[x]</tex>, тогда <tex>\|f(x)\|=deg(f(x))</tex> 
<tex>|a\cdot b|^2=|a|^2\cdot |b|^2\geq |b|^2</tex>, кроме того <tex>\|a\cdot b\|\geq \|b\|=|b|^2 \Rightarrow \|a\cdot b\|=|a\cdot b|^2</tex>
#<tex>\mathbb{Z}[i]: \|a+b\cdot i\|=a^2+b^2</tex>, т.e. <tex>\|z\|=|z|^2</tex>

==Алгоритм Евклида==
Изначально даны <tex>a,b\in R</tex>, необходимо найти их НОД. Пусть <tex>a<b</tex>. Поделим <tex>b</tex> на <tex>a</tex> с остатком 
<tex>b=a\cdot u_1 + r_1 (0\le r_1<a)</tex>, 
<tex>a=r_1\cdot u_2 + r_2 (0\le r_2<r_1)</tex>, 
........................... 
<tex>r_{n-1}=r_n\cdot u_{n+1} + r_{n+1} (0\le r_{n+1}<r_n)</tex>, 
<tex>r_n=r_{n+1}\cdot u_{n+2}</tex>. 
Число <tex>r_{n+1}</tex> является НОД чисел <tex>a</tex> и <tex>b</tex>. Алгоритм заканчивает свою работу, поскольку <tex>\forall a \in \mathbb{N} \cup \{-\infty\}</tex> может строго превосходить лишь конечное количество других таких чисел.

Евклидовы кольца

2010-10-14T00:07:09Z

Smetannikov.Ivan:

Неразложимые элементы, ассоциированные элементы и разложение на множители в целостных кольцах

2010-10-11T01:14:22Z

Smetannikov.Ivan: /* Ассоциированный элемент */

==Неразложимый элемент==
{{Определение
|definition=
Пусть <tex>R</tex> {{---}} [[Делители нуля, области целостности|область целостности]], тогда <tex>p \in R</tex> наывается неразложимым, если <tex>p\neq 1</tex> и из того, что <tex>p=a\cdot b \Rightarrow a=1</tex> или <tex>b=1</tex>.
}}
==Ассоциированный элемент==
{{Определение
|definition=
Если <tex>a\vdots b</tex> и <tex>b\vdots a</tex>, то <tex>а</tex> и <tex>b</tex> {{---}} ассоциированные элементы.
}}
{{Теорема
|id=th1
|statement=
Если <tex>a</tex> и <tex>b</tex> {{---}} ассоциированные, то <tex>a\div b</tex> {{---}} обратимый элемент.
|proof=
Пусть <tex>a = b\cdot c</tex>, <tex>b = a\cdot d</tex>, тогда <tex>a=b\cdot c=a\cdot d\cdot c \Rightarrow a\cdot (1-d\cdot c)=0 \Rightarrow 1-d\cdot c=0, d\cdot c=1 \Rightarrow c\cdot d</tex> {{---}} обратимый элемент.
}}

==Разложение на множители в целостных кольцах==
{{Определение
|definition=
<tex>R</tex> {{---}} кольцо с однозначным разложением на множители, если элемент представим в виде умножения неразложимых элементов.
}}

Неразложимые элементы, ассоциированные элементы и разложение на множители в целостных кольцах

2010-10-11T01:11:42Z

Smetannikov.Ivan:

==Неразложимый элемент==
{{Определение
|definition=
Пусть <tex>R</tex> {{---}} [[Делители нуля, области целостности|область целостности]], тогда <tex>p \in R</tex> наывается неразложимым, если <tex>p\neq 1</tex> и из того, что <tex>p=a\cdot b \Rightarrow a=1</tex> или <tex>b=1</tex>.
}}
==Ассоциированный элемент==
{{Определение
|definition=
Если <tex>ab</tex> и <tex>b a</tex>, то <tex>а</tex> и <tex>b</tex> {{---}} ассоциированные элементы.
}}
{{Теорема
|id=th1
|statement=
Если <tex>a</tex> и <tex>b</tex> {{---}} ассоциированные, то <tex>a\div b</tex> {{---}} обратимый элемент.
|proof=
Пусть <tex>a = b\cdot c</tex>, <tex>b = a\cdot d</tex>, тогда <tex>a=b\cdot c=a\cdot d\cdot c \Rightarrow a\cdot (1-d\cdot c)=0 \Rightarrow 1-d\cdot c=0, d\cdot c=1 \Rightarrow c\cdot d</tex> {{---}} обратимый элемент.
}}
==Разложение на множители в целостных кольцах==
{{Определение
|definition=
<tex>R</tex> {{---}} кольцо с однозначным разложением на множители, если элемент представим в виде умножения неразложимых элементов.
}}

Неразложимые элементы, ассоциированные элементы и разложение на множители в целостных кольцах

2010-09-28T22:33:13Z

Smetannikov.Ivan: Новая страница: «==Неразложимый элемент== {{Определение |definition= Пусть <tex>R</tex> - [[Делители нуля, области целост…»

==Неразложимый элемент==
{{Определение
|definition=
Пусть <tex>R</tex> - [[Делители нуля, области целостности|область целостности]], тогда <tex>p \in R</tex> наывается неразложимым, если <tex>p\neq 1</tex> и из того, что <tex>p=a\cdot b \Rightarrow a=1</tex> или <tex>b=1</tex>.
}}
==Ассоциированный элемент==
{{Определение
|definition=
Если <tex>a</tex> - [[Единицы (обратимые элементы), группа обратимых элементов|обратимый элемент]], то элементы <tex>a\cdot x</tex> и <tex>x\cdot a</tex> называются ассоциированными с <tex>x</tex>.
}}
==Разложение на множители в целостных кольцах==
{{Определение
|definition=
<tex>R</tex> - кольцо с однозначным разложением на множители, если элемент представим в виде умножения неразложимых элементов.
}}

Евклидовы кольца

2010-09-23T00:52:12Z

Smetannikov.Ivan: Новая страница: «{{Определение |definition= Евклидово кольцо - [[Определение кольца, подкольца, изоморфизмы ко…»

Единицы (обратимые элементы), группа обратимых элементов

2010-09-22T22:29:40Z

Smetannikov.Ivan: Новая страница: «{{Определение |definition= Обратимый элемент(единица кольца) - называется <tex>a\in R</tex>, где <tex>R<…»

{{Определение
|definition=
Обратимый элемент(единица кольца) - называется <tex>a\in R</tex>, где <tex>R</tex>-[[Определение кольца, подкольца, изоморфизмы колец|кольцо]], для которого существует обратный элемент, то есть такой элемент <tex>b \in R</tex>, что <tex>a\cdot b=b\cdot a=a</tex>.
}}
{{Определение
|definition=
Множество всех обратимых элементов кольца образует мультипликативную [[Группа|группу]], называемую группой обратимых элементов.
}}

Делители нуля, области целостности

2010-09-22T19:28:46Z

Smetannikov.Ivan: Новая страница: «==Делители нуля== {{Определение |definition= <tex>a \in R</tex> называется левым делителем нуля [[Опреде…»

==Делители нуля==
{{Определение
|definition=
<tex>a \in R</tex> называется левым делителем нуля [[Определение кольца, подкольца, изоморфизмы колец|кольца]] <tex>R</tex>, если <tex>\exists b \in R:b\neq 0 ; a\cdot b=0</tex>
}}
аналогично
{{Определение
|definition=
<tex>b \in R</tex> называется правым делителем нуля [[Определение кольца, подкольца, изоморфизмы колец|кольца]] <tex>R</tex>, если <tex>\exists a \in R:a\neq 0 ; a\cdot b=0</tex>
}}
Элемент, который является и правым, и левым делителем нуля одновременно, называется делителем нуля.
==Область целостности==
{{Определение
|definition=
[[Определение кольца, подкольца, изоморфизмы колец|Кольцо]], в котором <tex>0\neq 1</tex> и произведение двух ненулевых элементов не равно нулю называется областью целостности.
}}

Определение кольца, подкольца, изоморфизмы колец

2010-09-15T23:32:25Z

Smetannikov.Ivan:

{{Определение
|definition=
[[Множество]] <tex>R</tex>, на котором заданы бинарные операции сложение и умножение, с определенными свойствами, называется кольцом.
Свойства:
*<tex>\forall a,b \in R: a+b=b+a</tex> - коммутативность по сложению.
*<tex>\forall a,b,c \in R: a+(b+c)=(a+b)+c</tex> - ассоциотивность по сложению.
*<tex>\exists 0 \in R: a+0=0+a=a</tex> - существование нейтрального элемента по сложению.
* <tex>\forall a \in R\; \exists b \in R:a+b=b+a=0</tex> — существование [[Обратный элемент|обратного элемента]] относительно сложения;
* <tex>\forall a,b,c \in R:(a \cdot b) \cdot c=a \cdot (b \cdot c)</tex> — ассоциативность по умножению
* <tex>\forall a,b,c \in R</tex>
**<tex>a \cdot (b+c)=a \cdot b+a \cdot c</tex>
**<tex>(b+c) \cdot a=b \cdot a+c \cdot a </tex> — [[дистрибутивность]].
}}

==Подкольцо==
{{Определение
|definition=
[[Множество]] <tex>A \subset R</tex>, которое определено относительно операций, определенных в <tex>R</tex> называестя подкольцом.
}}

==Изоморфизм колец==
===Теорема===
Пусть <tex>R</tex> и <tex>R'</tex> - множества, в каждом из которых определены операции сложения и умножения. Пусть <tex>R</tex> изоморфно <tex>R'</tex>. Тогда, если <tex>R</tex> кольцо, то и <tex>R'</tex> кольцо.
Доказательство. 
Нужно убедится,что если выполняются аксиомы кольца для <tex>R</tex>, то они выполняяютсяи для <tex>R'</tex>. Докажем аксиому об существовании обратного элемента относительно сложения, остальное аналогично. Пусть <tex>a' \in R'</tex>, а <tex>a</tex> его прообраз в <tex>R</tex>, тогда по аксиоме об существовании обратного элемента относительно сложения <tex>\exists b: a+b=0</tex>. По изоморфизму <tex>\exists b': b \rightarrow b'</tex>, а также <tex>a'+b'=0'</tex>, значит в <tex>R'</tex> также выполняется эта аксиома.

==Примеры колец==
* <tex>\mathbb{Z}</tex> — целые числа.
* <tex>\mathbb{Z}_n</tex> — кольцо вычетов по модулю натурального числа <tex>n</tex>.
* <tex>\mathbb{Q}</tex> — кольцо рациональных чисел, являющееся полем.
* <tex>\mathbb{R}</tex> — кольцо вещественных чисел, являющееся полем.
* <tex>\mathbb{R}[x_1,x_2,...,x_n]</tex> — кольцо многочленов от <tex>n</tex> переменных над полем <tex>\mathbb{R}</tex>.

Определение кольца, подкольца, изоморфизмы колец

2010-09-15T21:26:35Z

Smetannikov.Ivan: Новая страница: «{{Определение |definition= Множество <tex>R</tex>, на котором заданы бинарные операции сложение и у…»