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

[INDIGO1991]

Здравствуюйте!

Задача:
Есть регулярный язык $L$ и язык $L_{1/2 - }$ , который задается следующим образом:
L_{1/2 -}= \left\{\alpha | \exists \beta : l(\alpha)=l(\beta) ; \alpha\beta \in L \right\}\
где $l(\alpha)$ - длинна слова $\alpha$, $\alpha\beta$ - "сцепка" слов.
Задача заключается в определении регулярности языка $L_{1/2-}$

Мне видеться, что язык наврядли регулярный, так как построить конечный автомат, который воспринимает половину слова, по автомату, который воспринимает все слово весьма проблематично (во всяком случае у меня не получилось это сделать).
А контрпример найти тоже не удается. Подскажите пожалуйста в каком направлении двигаться, чтобы решить эту задачу.

[Xaositect]

Можно попробовать воспользоваться тем, что язык регулярен тогда и только тогда, когда он имеет только конечное число остаточных языков (остаточным называется язык вида $L_a = \{x|ax\in L\}$)

-- Пн окт 05, 2009 17:05:50 --

Хотя нет, не особо помогает.

[INDIGO1991]

МММ... Сейчас пробую, что-нибудь с этим сделать.

-- Пн окт 05, 2009 18:17:14 --

Xaositect, а слово $a$ в этой теореме любое или просто существует как в моем языке?
з.ы. нам этой теоремы не давали, поэтому спрашиваю.

[Xaositect]

$a$ любое.

[INDIGO1991]

Нет через эту теорму ничего не получается.

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

-- Пн окт 05, 2009 20:02:21 --

безуспешно

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

Хорошая задача!

Вроде у меня получилось, что язык $L_{1/2}$ действительно регулярен. Правда, доказательство какое-то чересчур замудрёное.

Подробности пока не буду его публиковать, попробую поискать что-нибудь попроще (заодно поищу ошибки в своих рассуждениях) Если вкратце, то длины слов регулярного языка --- объединение конечного числа арифметических прогрессий. Пользуемся этим фактом и доказываем, что фиксированные доли слов языка (плюс-минус фиксированное число букв) образуют регулярный язык. Доказываем это индукцией по длине регулярного выражения, задающего язык.

[Xaositect]

О, значит я правильно думал ночью.
Случай конкатенации у меня не получилось разобрать.

[INDIGO1991]

Там если замкнутость относительно конкатинации прикручивать то не факт, что сможем все регулярные языки $L$ получить.

Сейчас буду прововать крутить с прогрессиями.

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

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

[INDIGO1991]

Чудо-в-перьях
множесто регулярных языков замкнуто относительно операции конкатинация

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

Спасибо, я забыла Задачу все равно решить не могу

[INDIGO1991]

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

[Xaositect]

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

[INDIGO1991]

ээээ. Все бы хорошо, но машина Тьюринга это следующая тема

[Xaositect]

Ну можно сразу автомат построить, но он сложно описывается.
Пусть множество состяний автомата, распознающего исходный язык $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\}$
Неформально: вместе с состоянием исходного автомата храним функцию, которая говорит, до каких состояний можно добраться из данного за количество шагов, равное уже сделанному.
Дальше сами, я и так уже слишком много написал.