Изменения

 ==Базовые определения==

|definition='''СимволАлфавит''' (англ. ''symbolalphabet'') {{---}} объектконечное непустое [[Множества|множество]] элементов, имеющий собственное содержание и уникальную читаемую форму.}} {{Определение|definition=называемых '''Алфавитсимволами''' (англ. ''alphabetsymbols'') . Условимся обозначать алфавит большой греческой буквой <tex>\Sigma</tex> {{---}} непустое множество символов.}}

ПримерыНаиболее часто используются следующие алфавиты:* # <tex>\Sigma = \left\{0, 1\right\} </tex> {{---}} бинарный или двоичный алфавит.* <tex>\Sigma = \left\{\cdot, -\right\} </tex> {{---}} алфавит, лежащий в основе азбуки Морзе.* # <tex>\Sigma = \left\{a, b, c, d, \dots..., z\right\} </tex> {{---}} английский алфавитмножество строчных букв английского алфавита.* <tex>\Sigma = \left\{0, 1, 2, \dots, 9\right\} </tex> {{---}} алфавит цифр.* Нотные знаки

|definition='''Нейтральный элементСлово''' (англ. ''string'') или '''цепочка''' {{---}} пустая строка <tex>\varepsilon : \varepsilon \in \Sigma^{0}</tex>. Для любой строки <tex>\alpha \in \Sigma^k</tex> верно <tex> : \alpha\varepsilon=\varepsilon\alpha=\alpha</tex>конечная последовательность символов некоторого алфавита.

|definition='''Замыкание КлиниПустая цепочка''' (англ. ''Kleene closureempty string'') {{---}} унарная операция над множеством строк либо символовцепочка, не содержащая ни одного символа. Замыкание Клини множества Эту цепочку, обозначаемую <tex>\Sigma</tex> есть <tex>\Sigma^* : \Sigma^* = \bigcup\limits_{n = 0}^\infty \Sigma^nvarepsilon </tex>, можно рассматривать как цепочку в любом алфавите.

|definition='''ЦепочкаДлина цепочки''' (англ. ''chainstring length'') {{---}} элемент конечной длины из число символов в цепочке. Длину некоторой цепочки <tex>w</tex> обычно обозначают <tex>\Sigma^*|w|</tex>.

|definition='''Конкатенация''' (англ. ''concatenation'') {{---}} бинарная, ассоциативная, некоммутативная операция, определённая на словах данного алфавита. Конкатецния строк <tex>\alpha \in \Sigma^k</tex> и {{---}} множество цепочек длины <tex>\beta \in \Sigma^mk</tex> является строка над алфавитом <tex>\alpha\beta \in \Sigma^{k + m}</tex>.

|definition='''Моноид''' (англ. ''monoid'') {{---}} множество, на котором задана бинарная ассоциативная операция, обычно именуемая умножением, и в котором существует нейтральный элемент. <tex>\Sigma^*= \bigcup \limits _{k=0}^\infty \Sigma^k</tex> с операцией конкатенации и нейтральным элементом — множество всех цепочек над алфавитом <tex>\varepsilonSigma</tex> образуют моноид.

|id=prefixdeflanguage|definition='''ПрефиксЯзык''' (англ. ''prefixlanguage'') строки над алфавитом <tex>\betaSigma</tex> {{---}} строка некоторое подмножество <tex>\alpha : \beta = \alpha \gammaSigma^*</tex>. Иногда такие языки называют '''формальными''' (англ. ''formal''), чтобы подчеркнуть отличие от языков в привычном смысле.

Пусть Отметим, что язык в <tex>\beta = Sigma</tex> не обязательно должен содержать цепочки, в которые входят все символы <tex>\underline{abr}acadabraSigma</tex>. Поэтому, тогда если известно, что <tex>L</tex> является языком над <tex>\alpha = abrSigma</tex>, то можно утверждать, что <tex>L</tex> {{---}} префикс это язык над любым алфавитом, являющимся надмножеством <tex>\betaSigma</tex>.

|id=suffixdefconcat|definition=Пусть <tex>x, y \in \Sigma^*</tex>. Тогда <tex> x \cdot y </tex> или <tex> xy </tex> обозначает их '''Суффиксконкатенацию''' (англ. ''suffixconcatenation'') строки , т.е. цепочку, в которой последовательно записаны цепочки <tex>\betax </tex> {{---}} строка и <tex>\alpha : \beta = \gamma \alpha y </tex>.

Пусть <tex>\beta = abracada\underline{bra}</tex>, тогда <tex>\alpha = bra</tex> {{---}} суффикс <tex>\beta</tex>Множество строк с операцией ''конкатенации'' образует [[Моноид|свободный моноид]].

== Операции над языками ==Пусть <tex>L</tex> и <tex>M</tex> {{---}} языки. Тогда над ними можно определить следующие операции.#Теоретико-множественные операции:#* <tex>L \cup M</tex> {{---}} объединение,#* <tex>L \cap M </tex> {{Определение---}} пересечение,|id=border#* <tex>L \setminus M</tex> {{---}} разность,|definition='''Бордер''' (англ. ''circumfix'') строки #* <tex>\betaoverline{L}=\Sigma^* \setminus L</tex> {{---}} строка дополнение.# Конкатенация: <tex>LM=\left\{\alpha\beta|\alpha \in L, \beta \in M\right\}</tex>.# Конкатенация с обратным языком: <tex>LR^{-1} = \{ w \beta mid \exists y \in R : wy \in L\}</tex>; конкатенация с обратным словом: <tex>Ly^{-1} = L\{y\}^{-1}, y \gamma in \alpha Sigma^*</tex>.# Степень языка: <tex>L^k= \alpha begin{cases}\{\varepsilon\eta }, k = 0\alpha \mu LL^{k-1}, k > 0.\alphaend{cases}</tex>.# Замыкание Клини: <tex>L^*=\bigcup\limits_{i=0}^{\infty}L^i</tex>.# [[#Гомоморфизм языков| Гомоморфизм]]

Пусть === Примеры ===* <tex>(\{0\}^*) \beta = cup (\{1\}^*)</tex> — язык состоит из последовательностей нулей, последовательностей единиц и пустой строки.* <tex>(\{0\}\{0\}^*) \cup (\underline{abra1\}cad\underline{abra1\}^*)</tex>— аналогично предыдущему, тогда но не содержит пустую строку.* <tex>(\{0\} \cup \{1\alpha })^* = abra\{0, 1\}^*</tex> — содержит все двоичные векторы и пустую строку.* Если <tex>L_p</tex> — язык десятичных представлений всех простых чисел, то язык <tex>(L_p \setminus (\{3\}\{---1,2,3,4,5,6,7,8,9,0\}} бордер ^*))</tex> будет содержать десятичные представления простых чисел, не начинающихся с тройки.* <tex>\beta{\mathrm{ab, ba, bba, abab, aa}\}a^{-1} = \{\mathrm{b, bb, a}\}</tex>.

|iddefinition=ind|definition=Пусть даны два алфавита <tex>\alpha[i]Sigma_1, \Sigma_2</tex> . '''Гомоморфизмом''' называется такое отображение <tex> \varphi \colon \Sigma_{1}^{*} \to \Sigma_{---2}^{*} обращение к символу под номером </tex>i, что:* <tex>\varphi(\varepsilon) = \varepsilon</tex> строки , то есть сохраняет пустую строку* <tex>\alphaforall w_1, w_2 \in \Sigma_1^*: \varphi(w_1w_2) = \varphi(w_1)\varphi(w_2)</tex>., то есть сохраняет конкатенацию

|iddefinition=period|definition='''ПериодОбразом языка''' <tex>L \subset \Sigma_1^* </tex> при гомоморфизме <tex>\varphi: \Sigma_1^* \to \Sigma_2^*</tex> (англ. иногда называют '''прямым гомоморфизмом'period'') строки называется язык <tex>M = \varphi(L) \overset{\underset{\mathrm{def}}{}}{=} \{ \varphi(x) \mid x \in L \}</tex>. <br>Заметим, что <tex>\alphavarphi</tex> {{---}} число будет [[Моноид#defmonhom | гомоморфизмом моноидов]] <tex>p : \forall i = 1 langle L, \cdot, \varepsilon \rangle</tex> и <tex>\ldots |langle M, \alpha| - pcdot, \alpha [i] = varepsilon \alpha[i + p]rangle</tex>.

|definition =Строка <tex>\alpha</tex> '''лексикографически меньшеПрообразом языка''' строки <tex>M \subset \betaSigma_2^*</tex> (при гомоморфизме <tex>\alpha < varphi: \Sigma_1^* \to \betaSigma_2^*</tex>(иногда называют '''обратным гомоморфизмом'''), если1. называется язык <tex>L = \alpha</tex> {varphi^{---1}} префикс <tex>(M) \overset{\beta</tex> ''или'' 2. <tex> underset{\mathcal mathrm{def}}{}}{9=} k : k \leqslant { x \mid \minvarphi(|x) \alpha|, |in M \beta|) }</tex> и . <br>Заметим, что <tex> \alphavarphi</tex> будет [k[Моноид#defmonhom | гомоморфизмом моноидов]] < tex>\langle L, \beta[k] cdot, \varepsilon \rangle</tex>, при этом и <tex> \mathcal {8} j < k : langle M, \cdot, \alpha_j = varepsilon \beta_j rangle</tex>

Строка <tex>\alpha = aca < \beta = acaaba</tex>, так как является префиксом <tex>\beta</tex>. Строка <tex>\alpha = acaa < \beta Примеры = acab</tex>, так как <tex>a < b</tex>. == Смотри также ==[[Период и бордер, их связь]] [[Слово Фибоначчи]]

* тривиальные гомоморфизмы** обнуляющий: <tex> \varphi(x) = \varepsilon, x \in L </tex>, тогда <tex> \varphi(L) = \{ \varepsilon \} </tex>** тождественный: <tex> \varphi(x) = x, x \in L </tex>, тогда <tex> \varphi(L) = L </tex> и <tex> \varphi^{-1}(L) = L</tex>* '''гомоморфизм цепочек''' {{---}} функция, подставляющая некоторую строку вместо каждого символа. Более формально, для заданного отображения <tex> h\colon \Sigma_1 \to \Sigma_1^* </tex> гомоморфизмом цепочек будет функция <tex> \varphi: \Sigma_1^* \to \Sigma_2^* </tex>, действующая от каждого символа строки из языка следующим образом <tex> \varphi(\overline{c_1 c_2 ... c_n}) = h(c_1)h(c_2) ... h(c_k) </tex>. Регулярные языки [[Слово Туэ-МорсаЗамкнутость регулярных языков относительно различных операций#st1 | замкнуты]]относительно гомоморфизма цепочек* ''солнечный язык'' из детских игр (когда после каждой гласной в слове надо добавлять букву "С" и эту же гласную) может быть представлен в виде гомоморфизма языков, где все согласные символы отображаются сами в себя, а гласный символ <tex> z </tex> переходит в <tex> zCz </tex> * циклический гомоморфизм: зафиксируем порядок символов в алфавите, будем отображать каждый символ в следующий, а последний {{---}} в первый. Обратным гомоморфизмом будет отображение каждого символа в предыдущий.

==ЛитератураСсылки ==* Гасфилд Д. Строки, деревья и последовательности в алгоритмах[[wikipedia: Информатика и вычислительная биология. — 2Formal_language_theory | Wikipedia {{---е изд.}} Formal language]]* Kelley, Dean (1995). Automata and Formal Languages[[wikipedia: An Introduction. LondonKleene_star | Wikipedia {{---}} Kleene star]]* [[wikipedia: PrenticeString_operations#String_homomorphism | Wikipedia {{-Hall International. ISBN 0-13-497777}} String homomorphism]]* [[wikipedia:ru:Формальный_язык | Википедия {{---7.}} Формальный язык]]* Gusfield, Dan (1999) [1997[wikipedia:ru:Звезда_Клини| Википедия {{---}} Звезда Клини]]* [http://www.google. Algorithms ru/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&ved=0CCsQFjAA&url=http%3A%2F%2Fehess.modelisationsavoirs.fr%2Fatiam%2Fbiblio%2FLothaire83-chap1.pdf&ei=UiV6UuvbAeaP4gSot4HwCA&usg=AFQjCNGUnEUG4oKbynqjDvd6NVMfSUuMJQ&sig2=GzMd4HvBNW2vYctSWDfvZQ&bvm=bv.55980276,d.bGE&cad=rjt M.Lothaire "Combinatorics on Stringswords"]* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' Введение в теорию автоматов, языков и вычислений, Trees and Sequences2-е изд. : Computer Science and Computational BiologyПер. с англ. {{---}} М. USA: Cambridge University PressИздательский дом «Вильямс», 2002. ISBN 0{{-521-58519-8}} С. 45.

[[Категория:Алгоритмы и структуры данныхТеория формальных языков]][[Категория:Основные определения. Простые комбинаторные свойства словАвтоматы и регулярные языки]]