Вопросы с тегом «automata»

10
Является ли обращение минимального DFA также минимальным?

Вопрос в значительной степени в названии. Есть ли время, когда некоторый язык может быть принят минимальным DFA с состояниями, но , обращение , может быть принято DFA с состояниями, где ?n L R L m m < nLLLNnnLрLRL^RLLLмmmм <...

10
Оптимальный решатель близоруких лабиринтов

Я дурачился с демоверсией Google Blocky's Maze и вспомнил старое правило, что если вы хотите решить лабиринт, просто держите левую руку на стене. Это работает для любого односвязного лабиринта и может быть реализовано конечным преобразователем. Пусть наш робот будет представлен преобразователем со...

10
Ясное, полное, доказательство того, что язык - это язык Тьюринга Конкурирует?

Я видел веб-сайты, которые якобы «доказывают», что HTML5 + CSS является Turing Complete. Я видел сайты, которые якобы «доказывают», что SQL завершен по Тьюрингу. Я видел множество веб-сайтов, которые якобы «объясняют», что значит быть завершенным по Тьюрингу. Достаточно! Где я могу найти книгу...

10
Можно ли превратить парсер Earley в нечеткий парсер, похожий на алгоритм Levenshtein Automata Algo для DFA?

Есть способ выполнить нечеткий синтаксический анализ (принимает строки даже с опечатками на определенном расстоянии редактирования), с помощью DFA и встроенных автоматов Левенштейна для входного слова. Может ли нечто подобное быть сделано с парсером Earley? Мне трудно понять алгоритм, не говоря уже...

10
Обычный язык не принят DFA, имеющий не более трех штатов

Опишите обычный язык, который не может быть принят ни одним DFA, имеющим только три состояния. Я не совсем уверен, с чего начать, и мне было интересно, если кто-то может дать мне несколько советов или советов. Я понимаю, что лемму прокачки можно использовать для доказательства того, что язык не...

10
Алгоритмы минимизации автоматов Мура

Алгоритм Бжозовского можно распространить на автоматы Мура, но его временная сложность в целом экспоненциальна. Есть ли другой алгоритм минимизации автоматов Мура? Какое время работы этих алгоритмов, если таковые...

9
Слова с одинаковым правым и левым ассоциативным произведением

Я начал изучать недетерминированные автоматы, используя книгу Хопкрофта и Уллмана . Я застрял в проблеме, которая показалась мне очень интересной: Дать недетерминированный конечный автомат, принимающий все строки, имеющие одинаковое значение, при оценке слева направо как справа налево путем...

9
Недетерминированные конечные автоматы | Пример SIPSER 1.16

Я работаю через Sipser Book (2-е издание) и наткнулся на этот пример, который я не понимаю. В книге говорится, что этот NFA принимает пустую строку εε\epsilon . Может ли кто-нибудь объяснить мне, почему это так? Насколько я понимаю, εε\epsilon перейдет к Q3Q3q_3 который не является состоянием...

9
Влияние размерности клеточных автоматов на классы сложности

Давайте возьмем в качестве примера сокращение 3d → 2d: какова стоимость моделирования трехмерного клеточного автомата двумерным клеточным автоматом? Вот несколько более конкретных вопросов: Какие алгоритмы будут изменять их временную сложность, на сколько? Какова будет основная идея для...

9
Какая связь между машинами Тьюринга с конечной лентой и конечными автоматами?

Кажется, я вспоминаю из студенческого класса, что для машины Тьюринга с конечной лентой всегда будут существовать соответствующие конечные автоматы, но я не смог найти это подтверждение где-либо в Интернете. Это на самом деле так, или я неправильно...

9
Если

Я застрял, решая следующее упражнение: Докажите, что если зависит от контекста, а R регулярно, то L / R = { w ∣ ∃ x ∈ RLLLRRR (т.е.правый фактор) не зависит от контекста.L/R={w∣∃x∈Rs.twx∈L}L/R={w∣∃x∈Rs.twx∈L}L / R = \{ w \mid \exists x \in R \;\text{s.t}\; wx \in L\} Я знаю , что должен...

9
Разница между языками, принятыми двумя DFA с разными начальными состояниями / принимающими государствами?

Недавно я задал вопрос по математике SE. Ответа пока нет. Этот вопрос связан с этим вопросом, но с техническими подробностями в отношении информатики. Даны два DFA A=(Q,Σ,δ,q1,F1)A=(Q,Σ,δ,q1,F1)A = (Q, \Sigma, \delta, q_1, F_1) и где набор состояний, входной алфавит и функция перехода и одинаковы,...

9
Что такое хороший алгоритм для генерации случайных DFA?

Я генерирую случайные DFA для проверки алгоритма сокращения DFA на них. Алгоритм, который я сейчас использую, таков: для каждого состояния , для каждого символа в алфавите c добавьте δ ( q , c ) к некоторому случайному состоянию. Каждое состояние имеет одинаковую вероятность стать конечным...

9
Условие бесконечности языка конечного автомата

Существует теорема, которая гласит: Дан конечный автомат, имеющий nnn указывает, существует ли строка www длина которого удовлетворяет n≤|w|≤2n−1n≤|w|≤2n−1n \leq |w| \leq 2n-1 тогда язык, принятый автоматом, бесконечен. Я понимаю ограничение |w|≥n|w|≥n|w| \geq n, но я не понимаю, почему ограничение...

9
Конвертировать CFG в КПК

Существует ли какой-либо набор правил или методов для преобразования любой контекстно-свободной грамматики в автомат для сжатия? В Интернете я уже нашел несколько слайдов, но не смог их понять. На слайде 10 он говорит о некоторых правилах, кто-нибудь может это...

9
Отличается ли недетерминированность в недетерминированной машине Тьюринга от конечных автоматов и автоматов с опущением?

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

9
Почему мы должны изучать все три формы представления конечных автоматов?

DFA, NFA и epsilon NFA - все три позволяют нам представлять определенный регулярный язык. С любым из этих представлений мы можем прийти к одному и тому же регулярному выражению, тогда зачем нам нужно изучать все три формы представления конечных автоматов? Может быть какое-то объяснение того, что...

9
DFA для принятия всех двоичных строк в форме степени (не делится на ), т.е. для данного

Мы можем сформировать DFA, принимающий двоичные числа, делимые на nnn . Например, DFA, принимающий двоичные числа, делимые на 2, может быть сформирован следующим образом: Аналогично, DFA, принимающий двоичные числа, делимые на 3, может быть сформирован следующим образом: Мы можем следовать четко...