Цель состоит в том, чтобы создать DFA из регулярного выражения, и использование «Regular exp> NFA> DFA преобразование» не вариант. Как это сделать? Я задал этот вопрос нашему профессору, но он сказал мне, что мы можем использовать интуицию, и любезно отказался дать какие-либо объяснения....
Если нет, то что это значит, когда для некоторого состояния и некоторого символа , не существует?Qqqδ ( q , a )aaaδ( д, )δ(q,a)\delta(q,
Я хочу преобразовать введенное пользователем регулярное выражение в NFA, чтобы потом можно было запускать NFA для строки для сопоставления. Какой минимальный компьютер можно использовать для разбора регулярных выражений? Я предполагаю, что это должен быть автомат с принудительной передачей, потому...
Если я правильно понимаю, NFA обладают той же выразительной силой, что и регулярные выражения. Зачастую считывание эквивалентных регулярных выражений из NFA легко: вы переводите циклы в звезды, соединения в качестве альтернатив и так далее. Но что делать в этом случае: [ источник ] Перекрывающиеся...
У меня сложилось впечатление, что наши компьютеры, будучи конечными, в конечном итоге не более мощные, чем (чрезвычайно большие) конечные автоматы. Тем не менее, линейно ограниченные машины Тьюринга также конечны, но кажется, что регулярные языки являются строго неподходящим подмножеством...
На работе мне было поручено вывести некоторую информацию о типах динамического языка. Я переписываю последовательности операторов во вложенные letвыражения, например так: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then {...
Итак, учитывая два DFA, является ли проблема обнаружения, если они генерируют один и тот же язык, разрешимой проблемой? Я уже знаю, что равенство двух КЛЛ не является разрешимым а как насчет равенства двух ДФА? учитывая, что большинство проблем с DFAs разрешимы, это тоже...
Минимизация детерминированных конечных автоматов (DFA) является проблемой, которая была тщательно изучена в литературе, и было предложено несколько алгоритмов для решения следующей проблемы: Учитывая DFA , вычислим соответствующий минимальный DFA, принимающий тот же язык, что и . Большинство этих...
У меня есть простая проблема создания DFA, который принимает все входные данные, начинающиеся с двойных букв (aa, bb) или заканчивающиеся двойными буквами (aa, bb), учитывая, что является набором алфавита данный язык.Σ = { a , b }Σзнак равно{a,б}\Sigma =\{a, b\} Я попытался решить это окольным...
Учитывая два набора строк над алфавитом Σ , можем ли мы вычислить наименьший детерминированный конечный автомат (DFA) M такой, что A ⊆ L ( M ) и L ( M ) ⊆ Σ ∗ ∖ B ?А , БA,ВA,BΣΣ\SigmaMMMA ⊆ L ( M)A⊆L(M)A \subseteq L(M)Л ( М) ⊆ Σ*∖ BL(M)⊆Σ*∖ВL(M) \subseteq \Sigma^*\setminus B Другими словами,...
Мне было интересно, так как * сама звезда-свободный язык, есть регулярный язык , который не является звездой свободного языка? Не могли бы вы привести пример?a∗a∗a^* (из википедии ) Лоусон определяет беззвездные языки как: Обычный язык называется свободным от звезд, если он может быть описан с...
Это может быть глупый вопрос. Это представляется очевидным , что FSA, так как оно конечно, может рассчитывать только количество символов в его входной строки до числа , ограниченного числа его состояний. Но теперь предположим, что мы оснастили FSA возможностями вывода (например, печати). Тогда было...
Существует ли клеточный автомат (в 2D), который имитирует силу между частицами?1 / р1/р1/r Более конкретно, я хотел бы знать, возможно ли при строго локальных правилах обновления два объекта (определенных в модели) притягивать друг друга с силой , где - расстояние, разделяющее объекты. Это, в...
Я видел веб-сайты, которые якобы «доказывают», что HTML5 + CSS является Turing Complete. Я видел сайты, которые якобы «доказывают», что SQL завершен по Тьюрингу. Я видел множество веб-сайтов, которые якобы «объясняют», что значит быть завершенным по Тьюрингу. Достаточно! Где я могу найти книгу...
Алгоритм Бжозовского можно распространить на автоматы Мура, но его временная сложность в целом экспоненциальна. Есть ли другой алгоритм минимизации автоматов Мура? Какое время работы этих алгоритмов, если таковые...
Опишите обычный язык, который не может быть принят ни одним DFA, имеющим только три состояния. Я не совсем уверен, с чего начать, и мне было интересно, если кто-то может дать мне несколько советов или советов. Я понимаю, что лемму прокачки можно использовать для доказательства того, что язык не...
Я ищу специальность в теоретической информатике; в частности, меня интересуют теория сложности и теория вероятностных автоматов. Когда я заканчиваю учебу в течение одного года, какие продвинутые курсы по математике (например, теория Галуа или гармонический анализ), по вашему мнению, было бы полезно...
Рассмотрим конечный автомат как обычно, но при каждом переходе он также может обновлять целочисленный счетчик, добавляя или вычитая число. Скажем, переходная функция вида перемещается в новое состояние и добавляет в счетчик, где (так что может быть положительным , отрицательный или...
Или, по крайней мере, сгенерируйте набор строк, которые принимает один NFA, чтобы я мог передать их в другой NFA. Если я сделаю поиск по каждому пути NFA, это будет работать? Хотя это займет много...
Я дурачился с демоверсией Google Blocky's Maze и вспомнил старое правило, что если вы хотите решить лабиринт, просто держите левую руку на стене. Это работает для любого односвязного лабиринта и может быть реализовано конечным преобразователем. Пусть наш робот будет представлен преобразователем со...