Вопросы по теме 'nfa'
Реализация NFA/DFA на C#
Кто-нибудь знает о какой-либо хорошей реализации NFA и DFA на С#, возможно, реализующей также преобразования между ними? Я хотел бы иметь возможность построить NFA, а затем автоматически преобразовать его в DFA, но без необходимости писать...
16585 просмотров
schedule
08.10.2022
Компромиссы временной сложности nfa против dfa
Я ищу обсуждение того, что лучше использовать и при каких обстоятельствах в компиляторе nfa или dfa. каковы компромиссы временной сложности при моделировании nfa и dfa и какой из них более подходит при каких обстоятельствах в компиляторе??
4565 просмотров
schedule
29.12.2023
Преимущества/недостатки NFA по сравнению с DFA и наоборот
Каковы относительные плюсы и минусы DFA и NFA по сравнению друг с другом?
Я знаю, что DFA легче реализовать, чем NFA, и что NFA медленнее достигают состояния принятия, чем DFA, но есть ли какие-либо другие явные, хорошо известные...
14913 просмотров
schedule
18.11.2022
r* выражение NFA
Я нашел это изображение, которое представляет выражение r* NFA. Мой вопрос: не должно быть стрелки, связывающей второй узел с третьим узлом? Таким образом, если у меня есть строка «rr», при чтении первого символа я попадаю во второй узел, но оттуда...
110 просмотров
schedule
17.10.2022
Сокращения в NFA, python
Я пытаюсь создать метод, в котором аббревиатуры перескакивали с одной точки на другую.
Я создал NFA с текущими краями
EDGES = [
(0, 'h', 1),
(1,'a',2),
(2,'z', 3),
(3,'a',4),
(4, 'r', 5),
(5, 'd', 6)
)]
Пример того, что я пытаюсь...
447 просмотров
schedule
16.05.2022
Покажите, что следующий набор над {a,b} является регулярным
Учитывая алфавит {a, b} , мы определяем N a (w) как количество вхождений a в слово w и аналогично для N b (w) . Покажите, что следующий набор над {a, b} регулярен.
A = {xy | N a (x) = N b (y)}
Мне трудно понять, с чего начать...
689 просмотров
schedule
05.12.2022
Как преобразовать NFA в регулярное выражение?
Я так запутался, как преобразовать NFA в регулярное выражение. У меня есть NFA, где начальное состояние также является конечным состоянием, и я не уверен, что мне следует делать. Вот как выглядит мой NFA:
Я попытался следовать рекомендациям,...
158 просмотров
schedule
07.12.2022
Как нарисовать DFA (или NFA) из простого оператора?
Мне дается простое утверждение: построить DFA над alphabet {0, 1} , который принимает all the strings that end in 101 ?
Мой вопрос заключается в том, каковы будут шаги по его разработке? Или разработайте NFA, потому что тогда я буду знать...
9908 просмотров
schedule
28.09.2023
Объявление стека структуры внутри определения структуры
Мне нужно объявить два стека структуры внутри ее собственного объявления структуры. Я знаю, что мог бы выполнить эту операцию с массивом, если я ссылаюсь на него с помощью указателя внутри структуры (т.е. FA *goingTo[30]; даст мне массив из 30 FA...
116 просмотров
schedule
21.04.2023
Как работают ɛ-переходы в недетерминированных конечных автоматах?
Меня смущает реализация языка автоматом. Переходит ли автомат сразу в следующее состояние, если есть ɛ-переход? Предположим, у меня есть автомат, состоящий из трех состояний a , b и c (где a — начальное состояние, а c — принимающее...
305 просмотров
schedule
30.10.2022
DFA :- все строки, в которых каждый блок из пяти последовательных символов содержит не менее двух нулей
Я хочу построить DFA для языка: набор всех строк, таких что каждый блок из пяти последовательных символов содержит не менее двух нулей. Как вести учет последних 5 записей. Короче как решить такую проблему. Я получил диаграмму DFA в Интернете, но...
12581 просмотров
schedule
09.08.2022
Преобразование регулярного выражения в DFA
Я пытался преобразовать регулярное выражение
к недетерминированному конечному автомату (NFA), сначала используя конструкцию Томпсона, что дает:
, что выглядит правильно.
Затем я использую построение подмножества для создания DFA из...
1922 просмотров
schedule
10.06.2024
Как разработать DFA, который принимает строки 1, 2, 3, а сумма делится на 6?
Как спроектировать NDF, который принимает строки 1, 2, 3, а сумма делится на 6? Например, 223311 принимается, а 322 не принимается. Могу ли я получить некоторую помощь?
Спасибо!
232 просмотров
schedule
26.12.2022
Регулярное выражение для DFA, которое принимает как пустую строку, так и другие строки
Для следующих DFA NFA
Я произвел RE
(a + b)(ab)*
Однако затем я понял, что мой RE не принимает пустую строку, поскольку он принимает только строки, начинающиеся с a или b , однако DFA NFA также принимает пустую строку,...
1046 просмотров
schedule
12.06.2022
schedule
31.05.2023
Значение комбинированных состояний в DFA
При преобразовании NFA в DFA иногда необходимо объединить состояния. Как в приведенном выше сценарии.
Но что на самом деле означает «объединение состояний в одно» в реальном сценарии?
И какова будет природа сочетания двух вышеуказанных...
137 просмотров
schedule
24.07.2023
вычисление ε-замыкания NFA в Haskell
Я реализую недетерминированный конечный автомат в Haskell, и я пытаюсь реализовать функцию, которая вычисляет замыкание эпсилон. С этой целью NFA реализуется как:
data Transaction = Transaction {
start_state :: Int,
symbol :: Maybe...
428 просмотров
schedule
21.01.2023
Как преобразовать диаграмму NFA в регулярное выражение?
Я просматриваю регулярные выражения и застрял на следующем вопросе:
Укажите регулярное выражение для описания языка следующего NFA: NFA Diagram
Я не знаю, как ответить на следующий вопрос, и я не хочу, чтобы кто-то дал мне на него ответ. Если...
343 просмотров
schedule
30.04.2022
c программа о grep
у меня проблемы с этим кодом, речь идет о строке поиска из файла после преобразования в dfa и nfa всякий раз, когда я пытаюсь получить доступ к значению argv, он дает "0x7fffffffe977" XDG_MENU_PREFIX = gnom "..." может быть, значение мусора? хотя я...
62 просмотров
schedule
04.06.2022