Регулярное выражение и X в степени N

Такого регулярного выражения не существует.

m/1+0+1+/ ?

Я могу ошибаться, но мне кажется, что такие выражения нельзя распознать при помощи ДКА без памяти, а значит нельзя представить в виде регулярного языка. Если бы посередине было 2*n нулей, где n>0, тогда это просто 11*00(00)*11*. А со степенью не получится, тут придётся использовать контекстно-свободный язык.

Да, это так. Путём итерации можно из двух нулей получить пустое множество, 00, 0000, и т.д. но тогда в этот язык будет входить, например, 000000, потому что нет никакого способа в ДКА без памяти запомнить предыдущую цепочку и на её основе принимать новую удвоенную, можно только перемещаться в конечном множестве состояний, отражающих "часть" цепочки, т.е. "ждём единицы в начале", "ждём двойные нули", "ждём единицы в конце". Для запоминания уже нужен магазин.

2seiken:

Пампинг леммой легко доказать, что {0}^(2^n) не регулярный:

разложение xyz, пусть в x содержится a нулей, в y -- b нулей, в z -- c нулей. Тогда по пампинг лемме (a+b) должно быть степенью двойки (можно нулевой), и (a+b+i*b) при любом i должно быть степенью двойки. Легко показать, что этого не может быть.

Возможно я чего-то не понял, но по идее "Тогда по пампинг лемме (a+b) должно быть степенью двойки ..." это если c=0, а если нет, то (a+b+c) - степень двойки и соответственно (a+b*i+c) должно быть степенью двойки при i>=0. Более того, a тоже может быть 0, тогда вообще всё просто: b - степень двойки и b*i - степень двойки, i>=0. Вроде так.

2seiken:

> Тогда по пампинг лемме (a+b) должно быть степенью двойки ..." это если c=0,

Нет, это я опечатался:(a+с) должно быть степенью двойки (если i=0).

> Более того, a тоже может быть 0, ...

А может и не быть!

0^{2^n} даже и не контекстно-свободный язык

>Нет, это я опечатался:(a+с) должно быть степенью двойки (если i=0).
Ok, тогда соответственно (a+c+b*i), i>0. Теперь я понял.

>> Более того, a тоже может быть 0, ...
>А может и не быть!
Я хотел сказать, что в цепочке xyz x и z необязательно должны быть непустыми, единственное - y должна быть непустой. Вроде так.

>0^{2^n} даже и не контекстно-свободный язык
? Что же его тогда машиной Тьюринга распознавать?

> Что же его тогда машиной Тьюринга распознавать?

Ну, например, программой на любом языке программирования, что эквивалентно машине Тьюринга :)

2seinken:

(a+b+c)=A;

A+b=A*2^n,n>0; => b=A*(2^n-1);

(a+2*b+c)+b=A*2^n+A*(2^n-1)=A*(2^(n+1)-1);

но (2^(n+1)-1)нечетное => A*(2^(n+1)-1) != 2^m

аналогично про не контекстно-свободный язык, uv^ixy^iz, |vxy| ≤ p, |vy| ≥ 1

Можно, если N известно заранее.

А можно ли составить конечный преобразователь (детерминированный или
нет), который по подобной цепочке на выход выдавал бы
цепочку единиц длины N (где N - показатель степени при описании
последовательности нулей).

Пример:
Вход - 1111000000001   // 8 нулей N = 3
Выход - 111            // N единиц

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

Сам подумай прежде чем такие вопросы задавать. Конечно можно. Причем элементарно. Тебя математический метод интересует или компьютенрная реализация ?

Математический естественно

У того автомата который мне в голову приходит просто дохрена состояний.
Когда поступает первый 0 - он переходит в состояние q1 и ничего не генерит на выходе, когда переходит еще один 0 он переходит в состояние q1 и генерит на выходе единичку, следующий 0 - переходит в состояние q2,  
еще один - в q3 и единичку на выход и т.д. Разумеется слова должны быть конечного размера не более некоторого N. По этому N подбирается число состояний автомата. Иначе он получится бесконечным автматом  

Короче на практике это просто счетчик i который выдает 1 когда i != 1 && (i & i-1 == 0)

>У того автомата который мне в голову приходит просто дохрена >состояний.
>Когда поступает первый 0 - он переходит в состояние q1 и ничего не 
>генерит на выходе, когда переходит еще один 0 он переходит в состояние 
>q1 и генерит на выходе единичку, следующий 0 - переходит в состояние 
>q2, еще один - в q3 и единичку на выход и т.д. Разумеется слова должны 
>быть конечного размера не более некоторого N. По этому N подбирается 
>число состояний автомата. Иначе он получится бесконечным автматом  

Это очевидно и тривиально.
Конечно на N есть только одно ограничение : N>0
То, что ты предложил правильно, но не для моей задачи!
Мне то нужно получить конечный преобразователь, который можно (???)
получить, как я думаю, путём какой-нибудь хитрой комбинации переходов 
из состояния в состояние с зацикливанием при определённых условиях.

Возможно ли это? Я не знаю.

В случае если N возможно бесконечно, то такого _коенчного_ автомата имхо существовать не может ибо ты вынужден считать 0, т.е. фиксировать то или иное состояние в зависимости от количества 0-й на входе => вслучае бесконечного числа 0-й нужно бесконечное число сотояний. Вообще вопрос интересный

Ага.

С теоретической точки зрения - какие условия должны накладываться
на множество входных цепочек, чтобы можно было с уверенностью сказать,
что не существует автомата, способного допустить ЛЮБУЮ цепочку из
этого множества?

Наверное завтра куплю какую-нибудь книгу, чтобы в теории 
лучше ориентироваться.

Купи Ахо-Сети-Ульмана и будет тебе щасте.

Плохо разбираюсь в теме, но в своё время мне помогла хоть как-то понять теорию книга Д. Хопкрофта, Р. Мотвани, Дж. Ульмана "Введение в теорию автоматов, языков и вычислений". Что касается условий, с помощью леммы о накачке можно доказать нерегулярность языка.