Публикации по теме 'dfa'
Не используйте конечные автоматы
Вместо этого используйте машины Тьюринга…
Название немного вводит в заблуждение. Это должно быть: «Не используйте детерминированные конечные автоматы (DFA). Вместо этого используйте машины Тьюринга».
Использование DFA там, где требуется машина Тьюринга, обойдется вам с точки зрения сложности кода.
И DFA, и машина Тьюринга являются конечными автоматами. Оба имеют состояния и переходы, разница в следующем:
DFA имеет только состояния и переходы. Его память ограничена только..
Вопросы по теме 'dfa'
Если язык (L) распознается NFA с n состояниями, может ли он также распознаваться DFA с не более чем 2 ^ n состояниями?
Я так думаю, потому что верхней границей будет 2 ^ n, и, учитывая, что это обе конечные машины, пересечение как для NFA с n состояниями, так и для DFA с 2 ^ n или меньше состояний будет действительным.
Я ошибаюсь здесь?
889 просмотров
schedule
28.08.2022
За что я должен отдавать предпочтение? (количество состояний) или (модульность‹-›читабельность)?
Как я уже говорил в этом вопросе , я использую DFA для отслеживания всех комментариев, строк и т. д. И я закончил этот DFA с 11 состояниями.
Теперь я собираюсь написать DFA для распознавания ключевых слов в java.
Идея:
Изначально pos=0....
79 просмотров
schedule
12.12.2022
Является ли регулярный язык всегда бесконечным
Меня немного смущает концепция обычного языка. Поскольку весь обычный язык может быть принят dfa, а в dfa всегда есть циклы. Таким образом, кажется, что dfa может принимать бесконечное количество строк. Означает ли это, что все обычные языки...
1882 просмотров
schedule
07.11.2022
Как я могу доказать, является ли этот язык правильным или нет?
Как я могу доказать, является ли этот язык правильным или нет?
L = {a n b n : n1} union {a n b n+2 : n1}
2954 просмотров
schedule
27.08.2022
Проектирование nfa, которое принимает пару строк
Мне нужна помощь в разработке nfa, который принимает слова «привет», «привет, мир» и «остаться вместе», алфавит включает английский алфавит, цифры и символы. Мне нужна помощь, чтобы начать. У кого-нибудь есть предложения?
458 просмотров
schedule
21.04.2024
Регулярное выражение для двоичных чисел, делящихся на 3
Я самостоятельно изучаю регулярные выражения и нашел в Интернете интересную практическую задачу, которая включает в себя написание регулярного выражения для распознавания всех двоичных чисел, делящихся на 3 (и только таких чисел). Честно говоря,...
23686 просмотров
schedule
27.01.2023
Как разработать DFA для следующего языка?
Как мне разработать DFA для:
Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
набор десятичных цифр.
L = {w| The decimal number represented by w leaves an odd remainder when divided by seven.}
Пока что я (вручную) нарисовал семь состояний (q0 -...
847 просмотров
schedule
29.06.2022
Парсер для регулярных выражений
Недавно я изучал основы и на практике решил реализовать DFA в контексте C ++. Так что в основном это регулярные выражения. Это хорошо работает, когда я строю дерево с нуля, однако я не знаю, как обращаться с регулярными выражениями.
Я имею в...
421 просмотров
schedule
31.08.2022
Создать синтаксическое дерево из заданных регулярных выражений (для RE в DFA)
Я изучаю теорию автоматов и сталкиваюсь с некоторыми трудностями при преобразовании RE непосредственно в DFA. Этот метод требует создания синтаксического дерева из RE. Но я не могу сгенерировать. Мне дают регулярное выражение, например,...
6245 просмотров
schedule
08.02.2023
может ли компилятор реально вычислить DFA из регулярного выражения?
При моддинге игры с закрытым исходным кодом я изменяю машинный код во время выполнения, чтобы jmp вписывался в мой собственный код. Чтобы сделать это в общем случае, я использую сопоставление с образцом, чтобы найти места кода, которые я хочу...
1373 просмотров
schedule
16.04.2024
Матрица теоремы Майхилла-Нероде для автоматов
Я успешно реализовал теорему Майхилла-Нероде на C ++. Когда завершается минимизация данного автомата, в качестве ответа выдается матрица.
Использование автоматов на этой странице: http://web.stcloudstate.edu/pkjha/CSCI502/Minimize.html , у меня...
246 просмотров
schedule
19.09.2022
Диапазоны и группы регулярных выражений для DFA реализованы в виде таблицы
В настоящее время я играю с преобразованием из регулярного выражения (без групп захвата, без возврата) в DFA, управляемый таблицей. Я реализовал это, создав NFA из регулярного выражения, а затем преобразовав NFA в DFA. В настоящее время я...
139 просмотров
schedule
02.02.2023
DFA для представления пароля
Я хочу создать DFA для пароля со следующими ограничениями:
он должен быть длиной 8 символов
он должен содержать не менее двух символов нижнего регистра: [a-z]
он должен содержать хотя бы один символ верхнего регистра: [A-Z]
он должен...
325 просмотров
schedule
31.10.2022
Эффективное сопоставление текстовых сообщений с тысячами регулярных выражений
Я решаю проблему, когда у меня есть текстовое сообщение, соответствующее тысячам регулярных выражений формы
<some string> {0 or 300 chars} <some string> {0 or 300 chars}
e.g.
"on"[ \t\r]*(.){0,300}"."[ \t\r]*(.){0,300}"from"...
424 просмотров
schedule
12.06.2022
Как я могу сделать DFA из следующего условия?
Пожалуйста, помогите мне сделать DFA из следующего условия:
L = {w: n a (w) по модулю 3 > n b (w) по модулю 3},
где n a (w) представляет количество вхождений a в w, а n b (w) представляет количество вхождений b в w.
326 просмотров
schedule
20.04.2022
Создать DFA для регулярного выражения действительного числа?
Я пытаюсь построить определенные конечные автоматы (DFA) действительного числа, которое определяется как:
Строка, начинающаяся с необязательных символов «+» или «-».
За которым следует один ноль или непустая последовательность цифр, которая не...
1037 просмотров
schedule
27.06.2023
DFA + счетчик с умножением, сложением, скобками
Я смотрю на экзаменационный вопрос, в котором говорится
'Объясните, как правильно составленное арифметическое выражение над переменными a, b, c, содержащее сложения, умножения и скобки, может быть распознано DFA со счетчиком. (Такой DFA может...
405 просмотров
schedule
27.04.2023
Как реализовать DFA, который распознает комментарии?
Мне понадобится помощь с Java здесь... Мне нужно реализовать DFA на Java, который распознает комментарии Java, содержащиеся между /* и */ . Чтобы начать с простых вещей, предположим, что алфавит DFA: {'/', '*', 'a'} , поэтому он распознает только...
163 просмотров
schedule
02.06.2023
Преобразование состояния DFA в регулярное выражение
У меня есть несколько вопросов относительно исключения состояния и терминологии.
В приведенном выше примере показан DFA с принимающим состоянием, в котором вы должны начать с символа 0 и закончить с 1.
Если бы мне нужно было преобразовать...
4288 просмотров
schedule
20.05.2022
Как разобрать входную строку на совпадения с DFA
Я реализую синтаксический анализатор регулярных выражений с нуля, создавая NFA из регулярного выражения, а затем DFA из NFA. Проблема в том, что DFA может только сказать, когда вычисление принимается. Если регулярное выражение — «n*», а строка для...
297 просмотров
schedule
17.05.2024
