WikiDer > Проклятое слово

Profinite word

В математика, точнее в формальная теория языка, проконечные слова являются обобщением понятия конечные слова в полное топологическое пространство. Это понятие позволяет использовать топология учиться языки и конечный полугруппы. Например, проконечные слова используются для альтернативной характеристики алгебраического понятия многообразие конечных полугрупп.

Определение

Позволять А ан алфавит. Набор проклятых слов закончился А состоит из завершение метрического пространства, областью определения которого является множество ${ displaystyle A ^ {*}}$ слов над А. Расстояние, используемое для определения метрики, дается с использованием понятия разделения слов. Теперь эти понятия определены.

Разделение

Позволять M и N быть моноиды, и разреши п и q быть элементами моноида M. Позволять φ быть морфизм моноидов из M к N. Говорят, что морфизм φ отделяет п и q если ${ displaystyle phi (p) neq phi (q)}$ . Например, морфизм ${ displaystyle phi: A ^ {*} to mathbb {Z} / 2 mathbb {Z}, w mapsto | w |}$ отправка слова с четностью его длины разделяет слова Ababa и абаа. В самом деле ${ Displaystyle фи (абаба) = 1 neq 0 = фи (абаа)}$ .

Он сказал, что N отделяет п и q если существует морфизм моноидов φ из M к N что отделяет п и q. Используя предыдущий пример, ${ Displaystyle mathbb {Z} / 2 mathbb {Z}}$ отделяет Ababa и абаа. В более общем смысле, ${ Displaystyle mathbb {Z} / п mathbb {Z}}$ разделяет любые слова, размер которых не совпадает по модулю п. В общем, любые два различных слова могут быть разделены с помощью моноида, элементы которого являются множителями п плюс новый элемент 0. Морфизм отправляет префиксы п себе и все остальное на 0.

Расстояние

Расстояние между двумя разными словами п и q определяется как величина, обратная размеру наименьшего моноида N разделение п и q. Таким образом, расстояние Ababa и абаа является ${ displaystyle { frac {1} {2}}}$ . Расстояние п и сам определяется как 0.

Это расстояние d является ультраметрический, то есть, ${ Displaystyle д (х, г) Leq макс влево {д (х, у), д (у, г) вправо }}$ . Кроме того, он удовлетворяет ${ displaystyle d (uw, vw) leq d (u, v)}$ и ${ Displaystyle d (ву, wv) leq d (и, v)}$ .С любого слова п можно отделить от любого другого слова с помощью моноида с | p | +1 элементы, где | p | это длина п, следует, что расстояние между п и любое другое слово по крайней мере ${ displaystyle { frac {1} {| p |}}}$ . Таким образом, топология, определяемая этой метрикой, есть дискретный.

Конечная топология

Бесконечное завершение ${ displaystyle A ^ {*}}$ , обозначенный ${ displaystyle { widehat {A ^ {*}}}}$ , это завершение множества конечных слов на расстоянии, определенном выше. Пополнение сохраняет структуру моноида.

Топология на ${ displaystyle { widehat {A ^ {*}}}}$ является компактный^{[уточнить]}.

Любой моноидный морфизм ${ displaystyle phi: от A ^ {*} до M}$ , с M конечно, однозначно продолжается до морфизма ${ displaystyle { widehat { phi}}: { widehat {A ^ {*}}} to M}$ , и этот морфизм равномерно непрерывный^{[уточнить]}. Более того, ${ displaystyle { widehat {A ^ {*}}}}$ наименьшее топологическое пространство с этим свойством.

Проклятое слово

Проклятое слово - это элемент ${ displaystyle { widehat {A ^ {*}}}}$ . А проклятый язык - это набор непонятных слов. Каждое конечное слово - бесконечное слово. Приведены несколько примеров нескончаемых слов, которые не являются конечными.

За м любое слово, пусть ${ displaystyle m ^ { omega}}$ обозначать ${ Displaystyle lim _ {я к infty} м ^ {я!}}$ . Обратите внимание, что ${ Displaystyle м ^ {я!}}$ это Последовательность Коши. Интуитивно отделить ${ Displaystyle м ^ {я!}}$ и ${ Displaystyle м ^ {я '!}}$ , моноид должен насчитывать как минимум до ${ Displaystyle мин (я, я ')}$ , следовательно, требуется как минимум ${ Displaystyle мин (я, я ')}$ элементы. С ${ Displaystyle м ^ {я!}}$ это Последовательность Коши, ${ displaystyle m ^ { omega}}$ действительно глубокое слово.

Кроме того, слово ${ displaystyle m ^ { omega}}$ идемпотентно. Это связано с тем, что при любом морфизме ${ displaystyle phi: от A ^ {*} до N}$ с N конечный, ${ Displaystyle фи (м ^ {я!}) = фи (м) ^ {я!}}$ . С N конечно, для я достаточно хорошо, ${ Displaystyle фи (м) ^ {я!}}$ идемпотентна, и последовательность постоянна.

По аналогии, ${ displaystyle m ^ { omega +1}}$ и ${ displaystyle m ^ { omega -1}}$ определены как ${ Displaystyle lim _ {п к infty} м ^ {п! +1}}$ и ${ Displaystyle lim _ {п к infty} м ^ {п! -1}}$ соответственно.

Проклятые языки

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

п непонятно.
п является узнаваемый,
В синтаксическая конгруэнтность из п открыто, как подмножество ${ displaystyle { widehat {A ^ {*}}} times { widehat {A ^ {*}}}}$ .

Аналогичные утверждения справедливы и для языков п конечных слов. Следующие условия эквивалентны.

${ displaystyle P}$ узнаваема (как подмножество ${ displaystyle A ^ {*}}$ ),
в закрытие из п, ${ displaystyle { overline {P}}}$ , узнаваема (как подмножество ${ displaystyle { widehat {A ^ {*}}}}$ ), куда
${ displaystyle P = K cap A ^ {*}}$ , для некоторого Clopen K,
${ displaystyle { overline {P}}}$ непонятно.

Эти характеристики происходят из-за более общего факта, что закрытие языка конечных слов и ограничение проконечного языка конечными словами являются обратными операциями, когда они применяются к распознаваемым языкам.

Navigation