сегодня опять никто не вкатывается в программирование, поэтому мы будем решать задачу для стажераТМ:дана регулярка, надо посчитать сколько строк длины Х под нее подходит. регулярки сегодня имеют следующий форматregex : 'a' | 'b' | '(' regex '*)' | '(' regex regex ')' | '(' regex '|' regex ')' ;
>>141305683 (OP)Ты ебанутый? 2 ^ X.
Я даже не знаю, что такое "регулярка", из задания вообще ничего не понял.Мимо программирую на Visual Basic.
>>141306024Двачаю1с сеньор
>>141305683 (OP)что можно сказать про распределение длин строк для регулярки r. рассмотрим сначала частные случаи.если регулярка константа - она равна только сама себе. в этом случае если Х равно длине константы, то строка одна, иначе ноль. запишем этот факт в виде F(Literal(s))=x^len(s)это такой формальный степенной ряд, также известный как производящая функция.
>>141306193если строка длины Х генерится с помощью Concat(r1,r2), то она может быть получена как строка длины 0, подходящая под r1 и строка длины X подходящая под r2, аналогично 1,X-1 итд.это дает формулу count(r1r2)(X) = count(r1)(0)count(r2)(X)+count(r1)(1)count(r2)(X-1)..= что представляет собой X-й коэффициент для произведения рядов для r1 и r2. таким образом получаем F(Concat(x,y))=F(x)*F(y)
>>141306527для альтернативы два распределения складываются: строки получаются из левой альтернативы и из правой. то есть F(Alt(x,y))=F(x)+F(y)
>>141306947теперь мы можем опередить функцию для замыкания.т.к. r* = epsilon + r+ r^2+.. то сделанные выше выводы позволяют нам заключить что F(Star(r)) = 1 + F(r) + F(r)^2 + ... эта геометрическая прогрессия очевидно сворачивается в 1/(1-F(r))
>>141305683 (OP)паскалееб/приплюснытый сишник в отставке, кодивший под mfc, но даже я смутно понял опа. в памяти что-то вспывает на тему "обратная польская запись"пора спать нахуй
>>141305683 (OP)Лучше бы это было такНОНЧЕ МЫ БУДЕМ ВКАТЫВАТЬСЯ В ПОГРОМИРОНЬЕ, И БУДЕМ ПИЛИТЬ СВОЙ ПАРСЕР\ХУЯРСЕР\АНАЛИЗАТОР ГОВНАМного уже слышал советов, что лучше свои проекты пилитьдаже если не знаешь чего пилить
>>141307298пример.возьмем регулярное выражение r=(a )((b(a )) ) и найдем сколько строк длины 10 под него подходит:F(r)=1/(1-a) (1/(1-b/(1-a)))=1/(1-a-b)это соовтетствует ряду 1/1-2x = sum i 2^i x^nт.е. под данное выражение подходят вообще все строки. впрочем 1/(1-a-b) как бы намекало на (a+b) *
тред одного семёна
>>141308428соврешенно верно.
Все задачки с хакерренка решаешь
>>141308526надо же как-то развлекаться.
>>141308541Росскожи о себе, работаешь или учишься? Поглядел, задачки вроде трудные
>>141308618а какой смысл простые делать.работаю в крупной компании, 200к в секунду.
>>141308390а теперь почему это решение не будет работать. причин для этого две.1. производящая функция, которую мы построили в этом решении, считает не количество разных строк, которые принадлежат языку, а количество разных выводов для этой грамматики. если одна строка может быть получена несколькими способами, например a star star или a star a star, то выведенная формула посчитает не то, что от нее требуется. чтобы этого избежать надо привести регулярное выражение к такому виду, в котором принятие любой строки будет происходить однозначно. во-первых, не очевидно почему в принципе должна быть возможна такая нормализация. во-вторых не очевидно как ее получить. например мне кажется что в этом случае стоит смотреть в сторону минимального dfa, просто потому что ничего лучше все равно нет, но никаких гарантий это не дает.2. вторая проблема состоит в том, что для получения замкнутого выражения k-го коэффициента разложения произвольной рациональной функции потребуется реализовать некоторое подмножество операций для символьных вычислений, которые можно найти в системах компьютерной алгебры, и которые иногда не совсем тривиальны. в частности в этом случае надо будет раскладывать на неприводимые дроби, т.е. факторизовывать многочлены, а это занятие для сильных духом.2.
>>141308702Не спорю, никакого. Просто интересно стало, какая база нужна для их решения,
>>141309040да никакой, берешь и решаешь.
>>141309015поэтому делать надо так.парсим регулярку, строим nfa, строим dfa, строим матрицу инцидентности, возводим ее в степень Х
>>141309378как известно, для графа возведение матрицы инцидентности в степень n дает в (i,j) количество путей длины n между этими нодами. что для автомата означает количество слов между состояниями. если в качестве начального состояния выбрать, как бы это не было странно, начальное, и просуммировать пути во все конечные, получится нужное число. конечно, с нами может случиться экспоненциальный взрыв, и в dfa закончится память. а если матрицу мы храним как dense, то еще раньше память закончится в матрице.
А можешь пояснить за клеточные автоматы?
>>141309710conway's game of life видел?
>>141309710Американская разрабоотка. Стреляешь по неграм, а они не умирают, а попадают в клетку. И все довольны.
>>141309767Ну да, я так понимаю что это простейший пример?
>>141309791кому и rule 110 простейший пример.
