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

Контексты и синтаксические моноиды

2010-09-30T20:07:13Z

Ivan.pomortsev:

[[Категория: Теория формальных языков]]
== Контексты ==
=== Правый ===
{{Определение
|definition=
'''Правым контекстом''' <tex>C_L^R(y)</tex> слова <tex>y</tex> в языке <tex>L</tex> называется множество <tex>\{z \mid yz \in L\}</tex>.
}}

{{Утверждение
|statement=
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L^R(y) \mid y \in \sum^*\}</tex> его правых контекстов конечно
|proof=
<tex>\Leftarrow</tex>:
Пусть множество правых контекстов языка конечно. Тогда построим распознающий его автомат. Состояний автомата будут соответствовать различным правым контекстам. Переход по некоторому символу из одного состояния в другое строится, если контекст, соответствующий первому состоянию, содержит элементы, которые получаются приписыванием этого символа в начало элементам контекста, соответствующего второму.
<br /><tex>\Rightarrow</tex>:
Пусть <tex>L</tex> {{---}} регулярный. Тогда существует автомат <tex>A</tex>, распознающий его. Рассмотрим произвольное слово <tex>y</tex>. Пусть <tex>u</tex> {{---}} состояние <tex>A</tex>, в которое можно перейти из начального по слову <tex>y</tex>. Тогда <tex>C_L^R(y)</tex> совпадает с множеством слов, по которых из состояния <tex>u</tex> можно попасть в допускающее. Причем если по какому-то слову <tex>z</tex> тоже можно перейти из начального состояния в <tex>u</tex>, то <tex>C_L^R(y) = C_L^R(z)</tex>. Наоборот, если <tex>C_L^R(y) = C_L^R(z)</tex>, то состояния, в которые можно перейти по словам <tex>y</tex> и <tex>z</tex>, эквивалентны. Таким образом, можно установить взаимное соответствие между правыми контекстами и классами эквивалентности вершин автомата, которых конечное число.
}}

=== Левый ===
{{Определение
|definition=
'''Левым контекстом''' <tex>C_L^L(y)</tex> слова <tex>y</tex> в языке <tex>L</tex> называется множество <tex>\{z \mid zy \in L\}</tex>.
}}

{{Утверждение
|statement=
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L^L(y) \mid y \in \sum^*\}</tex> его левых контекстов конечно
|proof=
Поскольку множество регулярных языков замкнуто относительно операции разворота, то из того, что <tex>C_L^L(y) = \overleftarrow{C_{\overleftarrow{L}}^R(\overleftarrow{y})}</tex> и аналогичного утверждения о правых контекстах получаем требуемое.
}}

=== Двухсторонний ===
{{Определение
|definition=
'''Двухсторонним контекстом''' <tex>C_L(y)</tex> слова <tex>y</tex> в языке <tex>L</tex> называется множество <tex>\{\langle x,z\rangle \mid xyz \in L\}</tex>.
}}

{{Теорема
|statement=
Язык <tex>L</tex> {{---}} регулярный <tex>\Leftrightarrow</tex> множество <tex>\{C_L(y) \mid y \in \sum^*\}</tex> его двухсторонних контекстов конечно
|proof=
<tex>\Leftarrow</tex>:
Если множество двухсторонних контекстов языка конечно, то конечно и множество его правых контекстов, а это значит, что язык регулярный.
<br /><tex>\Rightarrow</tex>:
Пусть <tex>L</tex> {{---}} регулярный. Тогда существует автомат <tex>A</tex>, распознающий его. Рассмотрим произвольное слово <tex>y</tex>. Пусть <tex>\langle i,y \rangle \vdash^* \langle u_i(y), \varepsilon \rangle, i = 1,2,\ldots,n</tex> (<tex>n</tex> - число состояний <tex>A</tex>). Если для какого-то слова <tex>z</tex> выполняется <tex>u_i(y) = u_i(z), i = 1,2,\ldots,n</tex>, то <tex>C_L(y) = C_L(z)</tex>. Наоборот, если <tex>C_L(y) = C_L(z)</tex>, то <tex>u_i(y) \sim u_i(z), i = 1,2,\ldots,n</tex>. Таким образом, можно установить взаимное соответствие между двухсторонними контекстами и классами эквивалентности наборов <tex>u_i</tex>, которых конечное число, поскольку каждое число <tex>u_i</tex> принимает значения от <tex>1</tex> до <tex>n</tex>.
}}

== Синтаксический моноид ==
{{Определение
|definition=
'''Синтаксическим моноидом''' языка <tex>L</tex> называется множество его двухсторонних контекстов с введенной на нем операцией конкатенации <tex>\circ</tex>, где <tex>C_L(y) \circ C_L(z) = C_L(yz)</tex>. Нейтральным элементом в нем является <tex>C_L(\varepsilon)</tex>
}}
Размер синтаксического моноида является мерой структурной сложности языка. Заметим, что если язык распознается автоматом из <tex>n</tex> состояний, размер его синтаксического моноида не превосходит <tex>n^n</tex>.

Эквивалентность состояний ДКА

2010-09-30T20:06:55Z

Ivan.pomortsev:

[[Категория: Теория формальных языков]]
== Эквивалентность автоматов ==

<font face="Times" size="3">

*'''Определение: ''' Два <em> автомата</em> <tex>\mathcal{A}_1(Q_1,\Sigma,\delta_1,s_10, T_1\subseteq Q_1)</tex> и <tex>\mathcal{A}_2(Q_2,\Sigma,\delta_2,s_20, T_2\subseteq Q_2)</tex> называются <em>эквивалентными</em>, если они распознают один и тот же язык над алфавитом <tex>\Sigma</tex>.
*'''Определение: ''' Два <em> состояния</em> <tex>s_i</tex> и <tex>s_j</tex> называются <em>эквивалентными</em> <tex>(s_i \sim s_j)</tex>, если <tex>\forall z\in \Sigma^*</tex> верно, что <tex>\delta(s_i, z)\in T \Leftrightarrow \delta(s_j, z)\in T</tex>. Из этого следует, что если два состояния <tex>s_i</tex> и <tex>s_j</tex> эквивалентны, то и состояния <tex>\delta_1(s_i, a)</tex> и <tex>\delta_2(s_j, a)</tex> будут эквивалентными для <tex>\forall a \in \Sigma</tex>. Кроме того, т.к. переход <tex>\delta(s, \varepsilon)</tex> может возникнуть только для конечного состояния <tex>s</tex>, то никакое допускающее(терминальное) состояние не может быть эквивалентно не допускающему состоянию. Нахождение классов эквивалентных состояний внутри автомата и их совмещение в одно состояние используется в быстром алгоритме Хопкрофта для минимизации автомата, работающий за <tex>O(n \log n)</tex>.
*'''Определение:''' Слово <tex>z \in \Sigma^*</tex> различает два состояния <tex>(s_i \nsim s_j)</tex>, если <tex>\delta(s_i, z)\in T \Leftrightarrow \delta(s_j, z)\notin T</tex>. Также, если слово <tex>z</tex> различает состояния <tex>t_1</tex> и <tex>t_2</tex> такие, что <tex>t_1=\delta(q_1, a)</tex> и <tex>t_2=\delta(q_2, a)</tex>, то слово <tex>aw</tex> различает состояния <tex>q_1</tex> и <tex>q_2</tex>. Нахождение пар различных состояний в автомате используется в алгоритме минимизации автомата, работающий за <tex>O(n^2)</tex>.

</font>

Автоматы с eps-переходами. Eps-замыкание

2010-09-30T20:06:32Z

Ivan.pomortsev:

{{В разработке}}
[[Категория: Теория формальных языков]]
Рассмотрим автомат, переходы в котором осуществляются по строкам.
{{Теорема
|id=th1
|about=О эквивалентности автоматов с переходами по строкам и НКА
|statement=
Автоматы с переходами по строкам эквивалентны недетерминированным автоматам.
|proof=
Рассмотрим два случая:
* <tex>\left | \alpha \right | \ge 1</tex>
* <tex>\left | \alpha \right | = 0 \Rightarrow \alpha = \varepsilon</tex>
Рассматриваем '''автомат А с <tex>\varepsilon</tex>-переходами.''' Для доказательства его эквивалентности НКА посторим его <tex>\varepsilon</tex>-замыкание.
{{Определение
|definition=
<tex>\varepsilon</tex>-замыкание (<tex>\varepsilon</tex>-closure) --- построение по автомату с <tex>\varepsilon</tex>-переходами эквивалентного ему автомата без <tex>\varepsilon</tex>-переходов.
}}
Ход построения <tex>\varepsilon</tex>-замыкания:
#Транзитивное замыкание
#Допускающие состояния
#Добавление ребер
#Устранение <tex>\varepsilon</tex>-переходов
Получили НКА эквивалентный исходному автомату.
}}
'''Следствие:''' множество языков, допускаемых автоматами с <tex>\varepsilon</tex>-переходами, совпадает с множеством языков, допускаемых ДКА.

Категория:Теория формальных языков

2010-09-30T20:05:54Z

Ivan.pomortsev: Содержимое страницы заменено на «Конечные автоматы, регулярные выражения, ...»

Конечные автоматы, регулярные выражения, ...

Категория:Теория формальных языков

2010-09-30T20:05:26Z

Ivan.pomortsev:

== Лекция 1 ==
*[[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов]]
*[[Операции над языками: теоретико-множественные операции, конкатенация, замыкание Клини]]
*[[Регулярные языки: два определения и их эквивалентность]]
*[[Детерминированные конечные автоматы]]
*[[Недетерминированные конечные автоматы]]
*[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]

== Лекция 2 ==
*[[Автоматы с eps-переходами. Eps-замыкание]]
*[[Теорема Клини (совпадение классов автоматных и регулярных языков]]
*[[Эквивалентность состояний ДКА]]
*[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]
*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
*[[Замкнутость регулярных языков относительно различных операций]]
*[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]

== Лекция 3 ==
*[[Доказательство нерегулярности языков: лемма о разрастании]]
*[[Интерпретация булевых формул с кванторами как игр для двух игроков]]
*[[Решение уравнений в регулярных выражениях]]
*[[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]
*[[Контексты и синтаксические моноиды]]

Теория формальных языков

2010-09-30T20:04:54Z

Ivan.pomortsev:

[[Категория: Теория формальных языков]]
== Лекция 1 ==
*[[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов]]
*[[Операции над языками: теоретико-множественные операции, конкатенация, замыкание Клини]]
*[[Регулярные языки: два определения и их эквивалентность]]
*[[Детерминированные конечные автоматы]]
*[[Недетерминированные конечные автоматы]]
*[[Построение по НКА эквивалентного ДКА, алгоритм Томпсона]]

== Лекция 2 ==
*[[Автоматы с eps-переходами. Eps-замыкание]]
*[[Теорема Клини (совпадение классов автоматных и регулярных языков]]
*[[Эквивалентность состояний ДКА]]
*[[Минимизация ДКА, алгоритм за O(n^2) с построением пар различимых состояний]]
*[[Минимизация ДКА, алгоритм Хопкрофта (сложность O(n log n))]]
*[[Замкнутость регулярных языков относительно различных операций]]
*[[Анализ свойств регулярных языков (пустота, совпадение, включение, конечность, подсчет числа слов)]]

== Лекция 3 ==
*[[Доказательство нерегулярности языков: лемма о разрастании]]
*[[Интерпретация булевых формул с кванторами как игр для двух игроков]]
*[[Решение уравнений в регулярных выражениях]]
*[[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]
*[[Контексты и синтаксические моноиды]]

Построение по НКА эквивалентного ДКА, алгоритм Томпсона

2010-09-30T20:04:28Z

Ivan.pomortsev:

[[Категория: Теория формальных языков]]
== Алгоритм Томпсона ==
Данный алгоритм используется для преобразования НКА в ДКА.
Для построения используются обход в ширину графа переходов.
Псевдокод:
<Цикл по всем состояниям>
* <Для всех переходов по одинаковым символам>
** <Объединить все состояния, куда они ведут в одно>
** <Если такого состояния нет в новом автомате>
*** <Добавить>
** <Иначе>
*** <Направить все переходы на него>

Так же для реализации можно использовать AVL-деревья

Категория:Теория формальных языков

2010-09-30T20:04:00Z

Ivan.pomortsev: Новая страница: «Конечные автоматы, регулярные выражения, ...»

Конечные автоматы, регулярные выражения, ...

Детерминированные конечные автоматы

2010-09-30T20:03:08Z

Ivan.pomortsev:

[[Категория: Теория формальных языков]]
== Детерминированный конечный автомат ==
{{Определение
|definition=
Детерминированный конечный автомат(ДКА) --- набор из пяти элементов <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle</tex>, где <tex>\Sigma</tex> -- алфавит, <tex>Q</tex> -- множество состояний автомата, <tex>s</tex> -- начальное состояние автомата, <tex>T</tex> -- Множество допускающих состояний автомата, <tex>\delta</tex> -- функция переходов.
}}
=== Процесс допуска ===
Процесс допуска слова автоматом выглядит так:
* Изначально автомат находится в стартовом состоянии
* Ему на вход подается строка
* Далее на каждом шагу автомат берет новый символ строки и совершает соответствующий переход в новое состояние, ''если для символа не задано никакого перехода из текущего состояния, то слово считается недопущенным (в отличие от [[Недетерминированные конечные автоматы|недетерминированного конечного автомата]], где множество переходов из текущего состояния может быть в том числе пустым)''
* Слово считается допущенным, если после того, как прочитаны все его символы, автомат оказался в допускающем состоянии.

Для удобства можно ввести следующие обозначения:
* <tex>\langle q, \alpha \rangle \vdash \langle p, \beta \rangle</tex>, если
** <tex>\alpha = c\beta</tex>
** <tex>\delta (q, c)=p </tex>

* <tex>\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle</tex>, если
** <tex>\langle q, c_1 c_2 c_3 ...c_n\beta \rangle \vdash \langle u_1, c_2 c_3 ...c_n\beta \rangle \vdash \langle u_2, c_3 ...c_n\beta \rangle ...\vdash \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \rangle</tex>

{{Лемма
|statement=
<tex>\langle q, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle, \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle \Rightarrow \langle q, \alpha\beta \rangle \vdash^* \langle r, \varepsilon \rangle</tex>
|proof=
<tex>\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.</tex>
}}

=== Автоматные языки ===
{{Определение
|definition=
<tex>L(\mathcal{A})=\{\alpha| \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle t \in T\}</tex> --- язык автомата <tex>\mathcal{A}</tex>.
}}

Детерминированные конечные автоматы

2010-09-30T19:58:18Z

Ivan.pomortsev: /* Процесс допуска */

== Детерминированный конечный автомат ==
{{Определение
|definition=
Детерминированный конечный автомат(ДКА) --- набор из пяти элементов <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle</tex>, где <tex>\Sigma</tex> -- алфавит, <tex>Q</tex> -- множество состояний автомата, <tex>s</tex> -- начальное состояние автомата, <tex>T</tex> -- Множество допускающих состояний автомата, <tex>\delta</tex> -- функция переходов.
}}
=== Процесс допуска ===
Процесс допуска слова автоматом выглядит так:
* Изначально автомат находится в стартовом состоянии
* Ему на вход подается строка
* Далее на каждом шагу автомат берет новый символ строки и совершает соответствующий переход в новое состояние, ''если для символа не задано никакого перехода из текущего состояния, то слово считается недопущенным (в отличие от [[Недетерминированные конечные автоматы|недетерминированного конечного автомата]], где множество переходов из текущего состояния может быть в том числе пустым)''
* Слово считается допущенным, если после того, как прочитаны все его символы, автомат оказался в допускающем состоянии.

Для удобства можно ввести следующие обозначения:
* <tex>\langle q, \alpha \rangle \vdash \langle p, \beta \rangle</tex>, если
** <tex>\alpha = c\beta</tex>
** <tex>\delta (q, c)=p </tex>

* <tex>\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle</tex>, если
** <tex>\langle q, c_1 c_2 c_3 ...c_n\beta \rangle \vdash \langle u_1, c_2 c_3 ...c_n\beta \rangle \vdash \langle u_2, c_3 ...c_n\beta \rangle ...\vdash \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \rangle</tex>

{{Лемма
|statement=
<tex>\langle q, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle, \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle \Rightarrow \langle q, \alpha\beta \rangle \vdash^* \langle r, \varepsilon \rangle</tex>
|proof=
<tex>\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.</tex>
}}

=== Автоматные языки ===
{{Определение
|definition=
<tex>L(\mathcal{A})=\{\alpha| \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle t \in T\}</tex> --- язык автомата <tex>\mathcal{A}</tex>.
}}

Детерминированные конечные автоматы

2010-09-30T19:55:48Z

Ivan.pomortsev: /* Процесс допуска */

== Детерминированный конечный автомат ==
{{Определение
|definition=
Детерминированный конечный автомат(ДКА) --- набор из пяти элементов <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle</tex>, где <tex>\Sigma</tex> -- алфавит, <tex>Q</tex> -- множество состояний автомата, <tex>s</tex> -- начальное состояние автомата, <tex>T</tex> -- Множество допускающих состояний автомата, <tex>\delta</tex> -- функция переходов.
}}
=== Процесс допуска ===
Процесс допуска слова автоматом выглядит так:
* Изначально автомат находится в стартовом состоянии
* Ему на вход подается строка
* Далее на каждом шагу автомат берет новый символ строки и совершает соответствующий переход в новое состояние, ''если для символа не задано никакого перехода из текущего состояния, то слово считается недопущенным (в отличие от [[Недетерминированные конечные автоматы|недетерминированного конечного автомата]], где множество переходов может быть пустым)''
* Слово считается допущенным, если после того, как прочитаны все его символы, автомат оказался в допускающем состоянии.

Для удобства можно ввести следующие обозначения:
* <tex>\langle q, \alpha \rangle \vdash \langle p, \beta \rangle</tex>, если
** <tex>\alpha = c\beta</tex>
** <tex>\delta (q, c)=p </tex>

* <tex>\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle</tex>, если
** <tex>\langle q, c_1 c_2 c_3 ...c_n\beta \rangle \vdash \langle u_1, c_2 c_3 ...c_n\beta \rangle \vdash \langle u_2, c_3 ...c_n\beta \rangle ...\vdash \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \rangle</tex>

{{Лемма
|statement=
<tex>\langle q, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle, \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle \Rightarrow \langle q, \alpha\beta \rangle \vdash^* \langle r, \varepsilon \rangle</tex>
|proof=
<tex>\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.</tex>
}}

=== Автоматные языки ===
{{Определение
|definition=
<tex>L(\mathcal{A})=\{\alpha| \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle t \in T\}</tex> --- язык автомата <tex>\mathcal{A}</tex>.
}}

Детерминированные конечные автоматы

2010-09-30T19:54:29Z

Ivan.pomortsev: /* Процесс допуска */

== Детерминированный конечный автомат ==
{{Определение
|definition=
Детерминированный конечный автомат(ДКА) --- набор из пяти элементов <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle</tex>, где <tex>\Sigma</tex> -- алфавит, <tex>Q</tex> -- множество состояний автомата, <tex>s</tex> -- начальное состояние автомата, <tex>T</tex> -- Множество допускающих состояний автомата, <tex>\delta</tex> -- функция переходов.
}}
=== Процесс допуска ===
Процесс допуска слова автоматом выглядит так:
* Изначально автомат находится в стартовом состоянии
* Ему на вход подается строка
* Далее на каждом шагу автомат берет новый символ строки и совершает соответствующий переход в новое состояние, ''если для символа не задано никакого перехода из текущего состояния, то слово считается недопущенным (в отличие от недетерминированного конечного автомата, где множество переходов может быть пустым''
* Слово считается допущенным, если после того, как прочитаны все его символы, автомат оказался в допускающем состоянии.

Для удобства можно ввести следующие обозначения:
* <tex>\langle q, \alpha \rangle \vdash \langle p, \beta \rangle</tex>, если
** <tex>\alpha = c\beta</tex>
** <tex>\delta (q, c)=p </tex>

* <tex>\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle</tex>, если
** <tex>\langle q, c_1 c_2 c_3 ...c_n\beta \rangle \vdash \langle u_1, c_2 c_3 ...c_n\beta \rangle \vdash \langle u_2, c_3 ...c_n\beta \rangle ...\vdash \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \rangle</tex>

{{Лемма
|statement=
<tex>\langle q, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle, \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle \Rightarrow \langle q, \alpha\beta \rangle \vdash^* \langle r, \varepsilon \rangle</tex>
|proof=
<tex>\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.</tex>
}}

=== Автоматные языки ===
{{Определение
|definition=
<tex>L(\mathcal{A})=\{\alpha| \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle t \in T\}</tex> --- язык автомата <tex>\mathcal{A}</tex>.
}}

Детерминированные конечные автоматы

2010-09-30T19:52:27Z

Ivan.pomortsev: /* Процесс допуска */

== Детерминированный конечный автомат ==
{{Определение
|definition=
Детерминированный конечный автомат(ДКА) --- набор из пяти элементов <tex>\langle \Sigma , Q, s \in Q, T \subset Q, \delta : Q \times \Sigma \to Q \rangle</tex>, где <tex>\Sigma</tex> -- алфавит, <tex>Q</tex> -- множество состояний автомата, <tex>s</tex> -- начальное состояние автомата, <tex>T</tex> -- Множество допускающих состояний автомата, <tex>\delta</tex> -- функция переходов.
}}
=== Процесс допуска ===
Процесс допуска слова автоматом выглядит так:
* Изначально автомат находится в стартовом состоянии
* Ему на вход подается строка
* Далее на каждом шагу автомат берет новый символ строки и совершает соответствующий переход в новое состояние, ''если для символа не задано никакого перехода из текущего состояния, то слово считается недопущенным''
* Слово считается допущенным, если после того, как прочитаны все его символы, автомат оказался в допускающем состоянии.

Для удобства можно ввести следующие обозначения:
* <tex>\langle q, \alpha \rangle \vdash \langle p, \beta \rangle</tex>, если
** <tex>\alpha = c\beta</tex>
** <tex>\delta (q, c)=p </tex>

* <tex>\langle q, \alpha \rangle \vdash^* \langle p, \beta \rangle</tex>, если
** <tex>\langle q, c_1 c_2 c_3 ...c_n\beta \rangle \vdash \langle u_1, c_2 c_3 ...c_n\beta \rangle \vdash \langle u_2, c_3 ...c_n\beta \rangle ...\vdash \langle u_{n-1}, c_n\beta \rangle \vdash \langle p, \beta \rangle</tex>

{{Лемма
|statement=
<tex>\langle q, \alpha \rangle \vdash^* \langle p, \varepsilon \rangle, \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle \Rightarrow \langle q, \alpha\beta \rangle \vdash^* \langle r, \varepsilon \rangle</tex>
|proof=
<tex>\langle q, \alpha\beta \rangle \vdash^* \langle p, \beta \rangle \vdash^* \langle r, \varepsilon \rangle.</tex>
}}

=== Автоматные языки ===
{{Определение
|definition=
<tex>L(\mathcal{A})=\{\alpha| \langle s, \alpha \rangle \vdash^* \langle t, \varepsilon \rangle t \in T\}</tex> --- язык автомата <tex>\mathcal{A}</tex>.
}}

Шаблон:Аватар

2010-09-13T21:58:17Z

Ivan.pomortsev:

<includeonly>
<div style="padding:5px; border:1px solid #000; display: inline-block;">[[Файл:{{{avatar}}}]]</div>
</includeonly>

Шаблон:Аватар

2010-09-13T21:57:53Z

Ivan.pomortsev:

<includeonly>
<div style="padding:5px; border:1px solid #000; display: inline;">[[Файл:{{{avatar}}}]]</div>
</includeonly>

Участник:Ivan.pomortsev

2010-09-13T21:57:20Z

Ivan.pomortsev:

Шаблон:Аватар

2010-09-13T21:56:51Z

Ivan.pomortsev:

<includeonly>
<div style="padding:5px; border:1px solid #000; ">[[Файл:{{{avatar}}}]]</div>
</includeonly>

Расширения полей

2010-09-13T21:53:58Z

Ivan.pomortsev:

{{В разработке}}

{{Определение
|definition=<tex> K \subset F</tex>, F называется расширением K (если <tex>[F : K]</tex> - конечна, то F - конечное расширение поля K)
}}

{{Определение
|definition=Степенью расширения называется величина <tex>[F:K]</tex>
}}

{{Утверждение
|statement=<tex>A \subset K \subset F \Rightarrow [F:A] = [K:A] \cdot [F:K]</tex>
}}

<tex>K \subset F, \alpha \in F</tex>, рассмотрим <tex>K(\alpha)</tex> {{---}} наименьшее подполе <tex>F</tex>, которое содержит <tex>K</tex> и <tex>\alpha</tex> (пересечение всех таких подполей содержится в <tex>K</tex> и <tex>\alpha </tex> <tex>\Rightarrow</tex> получается тоже подполе (замкнутое относительно операций сложения, умножения и обратно). <br />
Все возможные записи с <tex>K</tex> и <tex>\alpha</tex> образуют поле <tex>K(\alpha)</tex> : <tex>\frac{(K_1+\alpha)^7}{\alpha + K_2}</tex> и т.п. <br />
Если <tex>\alpha \in K \Rightarrow K(\alpha)=K, K \subset K(\alpha) \subset F, K(\alpha)</tex> {{---}} расширение поля <tex>K</tex>. (простое расширение {{---}} присоединение одного элемента). <br />
<tex>K \subset K(\alpha) </tex> <br />
# <tex>\exists f \in K[x] \colon f(\alpha) = 0</tex> {{---}} простое алгебраическое
# <tex>\nexists f</tex> {{---}} простое трансцендентное
# <tex>K(\alpha) \cong K(x) = \left\{\frac{p(x)}{q(x)} \mid p(x),q(x) \in K[x] \right\}</tex>
[[Категория: Поля]]

Расширения полей

2010-09-13T21:50:40Z

Ivan.pomortsev:

{{В разработке}}

{{Определение
|definition=<tex> K \subset F</tex>, F называется расширением K (если <tex>[F : K]</tex> - конечна, то F - конечное расширение поля K)
}}

{{Определение
|definition=Степенью расширения называется величина <tex>[F:K]</tex>
}}

{{Утверждение
|statement=<tex>A \subset K \subset F \Rightarrow [F:A] = [K:A] \cdot [F:K]</tex>
}}

<tex>K \subset F, \alpha \in F</tex>, рассмотрим <tex>K(\alpha)</tex> - наименьшее подполе <tex>F</tex>, которое содержит <tex>K</tex> и <tex>\alpha</tex> (пересечение всех таких подполей содержится в <tex>K</tex> и <tex>\alpha </tex> <tex>\Rightarrow</tex> получается тоже подполе (замкнутое относительно операций сложения, умножения и обратно). <br />
Все возможные записи с <tex>K</tex> и <tex>\alpha</tex> образуют поле <tex>K(\alpha)</tex> : <tex>\frac{(K_1+\alpha)^7}{\alpha + K_2}</tex> и т.п. <br />
Если <tex>\alpha \in K \Rightarrow K(\alpha)=K, K \subset K(\alpha) \subset F, K(\alpha) - </tex>расширение поля <tex>K</tex>. (простое расширение - присоединение одного элемента). <br />
<tex>K \subset K(\alpha) </tex> <br />
# <tex>\exists f \in K[x] f(\alpha) = 0</tex> - простое алгебраическое
# <tex>\nexists f</tex> - простое трансцендентное
# <tex>K(\alpha) \cong K(x) = \left\{\frac{p(x)}{q(x)} \mid p(x),q(x) \in K[x] \right\}</tex>
[[Категория: Поля]]

Участник:Ivan.pomortsev

2010-09-13T21:33:50Z

Ivan.pomortsev: Новая страница: «Файл:avatar.jpg»

[[Файл:avatar.jpg]]

Файл:Avatar.jpg

2010-09-13T21:32:57Z

Ivan.pomortsev:

Поле частных кольца, поле Q как поле частных кольца Z

2010-09-13T21:27:16Z

Ivan.pomortsev:

{{В разработке}}

[[Категория: Поля]]

Расширения полей

2010-09-13T21:27:00Z

Ivan.pomortsev:

Поле как линейное пространство над своим подполем

2010-09-13T21:26:43Z

Ivan.pomortsev:

{{В разработке}}
[[Категория: Поля]]

Характеристика поля, простые поля, классификация простых полей

2010-09-13T21:26:24Z

Ivan.pomortsev:

{{В разработке}}
[[Категория: Поля]]

Мультипликативная группа поля

2010-09-13T21:26:01Z

Ivan.pomortsev:

{{В разработке}}
{{Определение
|definition=
Мультипликативная группа <tex>\mathbb{K^*}</tex> [[поле|поля]] <tex>\mathbb{K}</tex> — это группа, содержащая все ненулевые элементы из <tex>\mathbb{K}</tex>, и операция в ней совпадает с операцией умножения в <tex>\mathbb{K}</tex>.
}}

[[Категория: Теория групп]]
[[Категория: Алгебра]]
[[Категория: Поля]]

Примеры полей

2010-09-13T21:25:41Z

Ivan.pomortsev:

{{В разработке}}
Примеры полей:
# <tex> \mathbb{R} \subset \mathbb{C} </tex> <tex>[\mathbb{C} : \mathbb{R}] = 2</tex>
# <tex> \mathbb{Q} \subset \mathbb{R} </tex> <tex>[\mathbb{R} : \mathbb{Q}] = +\infty</tex>
[[Категория: Поля]]

Категория:Поля

2010-09-13T21:25:12Z

Ivan.pomortsev:

{{Определение
|definition=
Расширим понятие кольца: введём обратный элемент <tex>(F, *, +)</tex> — получим '''поле'''
# абелево по <tex>+</tex>
# <tex>F\setminus\{0\}</tex> — абелево по <tex>*</tex>
# дистрибутивно
}}

Примеры:
* Поля: <tex>\mathbb{R}, \mathbb{C}, \mathbb{Q}, \mathbb{Z}_n^*</tex>
* <tex>\mathbb{Q}(x)=\{\frac{p(x)}{q(x)} \mid p,q \in \mathbb{Q}[x]\}</tex>
* <tex>\mathbb{Q}(\sqrt{d})=\{a+b\sqrt{d}\mid a,b \in \mathbb{Q}\}</tex>

Определение поля и подполя, изоморфизмы полей

2010-09-13T21:24:30Z

Ivan.pomortsev:

{{В разработке}}
{{Определение
|definition=
Расширим понятие кольца: введём обратный элемент <tex>(F, *, +)</tex> — получим '''поле'''
# абелево по <tex>+</tex>
# <tex>F\setminus\{0\}</tex> — абелево по <tex>*</tex>
# дистрибутивно
}}

Примеры:
* Поля: <tex>\mathbb{R}, \mathbb{C}, \mathbb{Q}, \mathbb{Z}_n^*</tex>
* <tex>\mathbb{Q}(x)=\{\frac{p(x)}{q(x)} \mid p,q \in \mathbb{Q}[x]\}</tex>
* <tex>\mathbb{Q}(\sqrt{d})=\{a+b\sqrt{d}\mid a,b \in \mathbb{Q}\}</tex>

Мультипликативная группа поля состоит из ненулевых элементов по умножению.

<tex>1 \in F</tex>

<tex>n \cdot 1</tex> — обозначение суммы
<tex> n \cdot 1 = m \cdot 1 \Rightarrow (n-m) \cdot 1 = 0 </tex>

Все разные <tex>\begin{cases}
1 \\
1 + 1 \\
1 + 1 + 1 \\
\vdots
\end{cases} \begin{aligned} \nearrow \exists n : n \cdot 1 = 0 \\
\searrow \nexists n : n \cdot 1 = 0 \end{aligned} </tex>

В первом случае наименьшее такое n называется характеристикой поля и обозначается <tex>char\; F</tex>.
Во втором случае характеристика поля полагается равной 0.

<tex>\mathbb{Q}, \mathbb{C}, \mathbb{R} </tex> имеют характеристику 0 <br />
<tex>\mathbb{Z}_p</tex> имеет характеристику p <br />
<tex>\mathbb{Q}(x)</tex> имеет характеристику 0 <br />
<tex>\mathbb{Q}(\sqrt{d})</tex> — характеристику 0 <br />

{{Теорема
|statement=<tex> char\; F</tex> либо 0, либо простое число:
<tex>\left [ \begin{aligned} char\; F = 0\\ char\; F \in \mathbb{P} \end{aligned} \right .</tex><br />
|proof=<tex>(n \cdot m) \cdot 1 = 0</tex> <br />
<tex> (n \cdot 1) \cdot (m \cdot 1) = 0 \Rightarrow \left [ \begin{aligned} n \cdot 1 = 0 \\ m \cdot 1 = 0\end{aligned} \right . \Rightarrow</tex> характеристика <tex>\ne n \cdot m</tex> — противоречие с минимальностью <tex> char\; F </tex>
}}
Подполе - некоторое поле <tex> K \subset F </tex>, замкнутое относительно сложения и умножения:
# <tex>0,1 \in K</tex>
# <tex>a,b \in K \Rightarrow a+b \in K </tex>
# <tex>a,b \in K \Rightarrow a*b \in K </tex>
# <tex>a \in K \Rightarrow -a \in K </tex>
# <tex>a \in K \Rightarrow a^{-1} \in K </tex>
<tex>\mathbb{Q} \subset \mathbb{R}</tex> - подполе.

Поле называется простым, если оно не содержит тривиальных подполей.
<tex>\mathbb{Q} \subset \mathbb{Q}(x)</tex> - подполе <tex>\Rightarrow \mathbb{Q}(x)</tex> - не простое поле.

{{Определение
|definition=
Два поля называются одинаковыми, если существует биекция из одного поля в другое, сохраняющая операции сложения и умножения. <tex>K \cong F \Leftrightarrow \exists \varphi \colon K \to F; \varphi (a + b) = \varphi (a) + \varphi (b); \varphi (a b) = \varphi (a) \cdot \varphi (b) </tex>
}}

{{Утверждение
|statement=<br />
# <tex>char\; F = 0 \Rightarrow F \cong \mathbb{Q}</tex><br />F - простое
# <tex>char\; F \ne 0 \Rightarrow F \cong \mathbb{Z}_P</tex><br />F - простое
|proof=<br />
# <tex> char \; F = 0 \Rightarrow </tex> суммы все различны; <tex>n \cdot 1 \ne 0, n \ne 0</tex><br /><tex>\frac{n}{m}\cdot1=\frac{n\cdot1}{m\cdot1}</tex><br /><tex>\frac{kn \cdot 1}{km \cdot 1} = \frac{(k \cdot 1) \cdot (n \cdot 1)}{(k \cdot 1) \cdot (m \cdot 1)} = \frac{n \cdot 1}{m \cdot 1}</tex><br /><tex>q \cdot 1 \ne 0, q \ne 0 \Rightarrow </tex>построенное поле <tex>\cong \mathbb{Q}</tex>
# <tex> char \; F = p \qquad n \cdot 1 = m \cdot 1 \Leftrightarrow n \equiv m (mod \;p) </tex>. Замкнуто относительно сложения и умножения <tex> \Rightarrow </tex> подполе <tex> \cong \mathbb{Z}_p </tex><br /><tex> K \subset F </tex>, F - вектор-пространство надо полем K. (F - вектора, K - скалярные величины). <br /> <tex> V_1 + V_2 \in F; K \cdot V_1 \in F \Rightarrow </tex> получаем векторное пространство. <br /><tex>[F:K]</tex> - размерность поля F над полем K.
}}

[[Категория: Поля]]

Категория:Поля

2010-09-13T21:22:57Z

Ivan.pomortsev: Новая страница: «Поле»

Поле

Расширения полей

2010-09-13T21:20:08Z

Ivan.pomortsev:

Примеры полей

2010-09-13T21:15:03Z

Ivan.pomortsev:

Расширения полей

2010-09-13T21:10:15Z