Регулярные языки

[Профессор Снэйп]

INDIGO1991 в сообщении #249628 писал(а):

Профессор Снэйп
вы не могли бы написать чуть подробней ваше доказательство?
У меня не совсем получается его восстановить по вашему очерку.

Оно у меня в голове вертелось, я на бумагу не пытался его записывать. Боюсь, что если начать это делать, то там вылезут многочисленные сложности...

Одна из идей, упрощающих доказательство, была такая. Если $L$ --- регулярный язык, то $L = L_1 \cup \ldots \cup L_k$, где для любого $i$ от $1$ до $k$ длины слов из языка $L_i$ образуют арифметическую прогрессию. Далее, конкатенация с объединением подчиняются свойству дистрибутивности. И ещё: если $L_{m/n \pm s}$ регулярен, то $(L_i)_{m/n \pm s}$ регулярен для любого $i$. Так что случай конкатенации можно свести к конкатенации языков, длины слов каждого из которых образуют одну арифметическую прогрессию.

Ну а дальше уже начинаются разные кропотливые сложности, которые я до конца не расписывал. Возможно, там всякая дрянь навылазит, если расписывать начать. Надо садиться с листом бумаги за стол и конкретно думать, мне лень (нет времени).

Кстати, почему именно с конкатенацией сложности? Звёздочка Клини, как мне кажется, ничуть не проще.

Там вон выше Xaositect построил автомат в явном виде, лучше с ним поразбираться сначала Может, и не нужны будут все эти мои заморочки

Xaositect в сообщении #249642 писал(а):

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

Вот это мне самому очень интересно. Как её строить, такую линейную МТ? Если к данному слову дописывать по очереди все слова такой же длины и проверять для каждой конкатенации принадлежность исходному языку, то тут даже полиномиальной сложности не будет, не то что линейной

Вот, кстати, факт: если язык $L$ регулярен, то язык $\{ wv : w \in L,\, l(w) = l(v) \}$ уже может быть не регулярным (пример --- язык, задаваемый регулярным выражением $a^\ast b$). То есть если просто искать половинки слов и проверять (за линейное время) их принадлежность языку $L$, то линейность теряется. То есть половинка слова просто так за линейное время не находится. А то, что Вы собрались за линейное время делать, выглядит гораздо сложнее!!!

-- Ср окт 07, 2009 09:11:33 --

Xaositect в сообщении #249657 писал(а):

Неформально: вместе с состоянием исходного автомата храним функцию, которая говорит, до каких состояний можно добраться из данного за количество шагов, равное уже сделанному.

А как Вы можете знать, какое количество шагов уже сделано? В автоматах, знаете ли, циклы разные бывают. Pumping lemma опять же

Хотя в формальную конструкцию пока не вникал. Может, оно всё и нормально там...

-- Ср окт 07, 2009 09:24:30 --

Ага! Прочитал формальную конструкцию. Вроде понял, вроде всё правильно

Там подправьте, кстати, кое-где. У Вас функция $\varphi$ то одноместная, то двухместная: в разных местах по разному

[Xaositect]

Профессор Снэйп в сообщении #249675 писал(а):

Вот это мне самому очень интересно. Как её строить, такую линейную МТ?

Сначала идем вправо как автомат, потом влево до началаа как недерминированный автомат, считая, что на каждом шаге нам как бы попадаются все символы алфавита.
Ну а после этой МТ до описанного автомата - еще пара шагов.

Профессор Снэйп в сообщении #249675 писал(а):

Там подправьте, кстати, кое-где. У Вас функция то одноместная, то двухместная: в разных местах по разному

Править уже не могу, кому надо - разберутся

[Профессор Снэйп]

Xaositect в сообщении #249726 писал(а):

Править уже не могу, кому надо - разберутся

Кстати, мне показалось, что у Вас чересчур сложная конструкция. Достаточно брать $Q' = Q \times 2^Q$, состояний будет меньше.

[Xaositect]

Да, достаточно.

[INDIGO1991]

В решении вот только разобрался, подставив пару канкретных языков!

Огромное вам спасибо!!!

[Чудо-в-перьях]

Xaositect в сообщении #249657 писал(а):

Ну можно сразу автомат построить, но он сложно описывается.
Пусть множество состяний автомата, распознающего исходный язык $L$, есть $Q$, функция перехода - $\varphi\colon Q\times A\to Q$, начальное состояние $q_0$, мн-во принимающих - $F$
Рассмотрим функцию $\nu\colon 2^Q\to 2^Q$: $\nu(T) = \{\varphi(q,a)|q\in T, a\in A\}$
Рассмотрим автомат с множеством состояний $Q' = Q\times (Q\to 2^Q)$, функцией перехода $\varphi'(<q, f>, a) = <\varphi(q), \nu \circ f>$, начальным состоянием $<q_0, \sigma>$, где $\sigma(q) = \{q\}$, множеством принимающих состояний $F' = \{<q, f> | f(q)\cap F \neq \varnothing\}$
Неформально: вместе с состоянием исходного автомата храним функцию, которая говорит, до каких состояний можно добраться из данного за количество шагов, равное уже сделанному.
Дальше сами, я и так уже слишком много написал.

О, спасибочки))) даже я вспомнила, даже то, что не знала))))