Описание тега nfa
NFA - это недетерминированный конечный автомат, математическая модель вычислений, которая определяет принадлежность к обычным языкам.
0
ответов
NFA для базы m не делится на n
Мне дали упражнение найти DFA for base m no divisible by m, Благодаря этой ссылке я узнал, как это сделать, но потом подумал, как бы мы подошли к этому упражнению, если бы оно создавало NFA а затем преобразовать его в DFA, используя метод построения…
23 сен '18 в 07:30
1
ответ
Как скрыть регулярное выражение в простейшей форме?
Я сделал это выражение из NFA (NFA для регулярного выражения): (a+ab+aa*b)*(a+a*a) но в ответах книги написано так: (a+aa*b)*(a+a*a) Я думаю, что мой ответ такой же, как и у книги, но они преобразовали его в него, как квадратное уравнение, как и мы.…
29 апр '14 в 11:18
2
ответа
Это правильный график NFA?
Задача: Построить NFA из заданного регулярного выражения. Я решил перенести некоторые из моих старых программ на GitHub. Конкретно проблемы, касающиеся теории формальных языков. После тестирования кода у меня был такой результат, и я не могу точно с…
07 окт '18 в 14:10
1
ответ
Значение комбинированных состояний в DFA
При конвертации и NFA в DFA, иногда государства должны быть объединены. Как в приведенном выше сценарии. Но что на самом деле означает "объединять государства в одно" в реальном сценарии? И какова будет природа комбинации двух вышеупомянутых госуда…
08 ноя '17 в 05:59
3
ответа
Минимизация DFA
У меня есть вопрос о минимизации DFA. Поэтому я использовал очень хорошо известные методы для преобразования регулярного выражения в NFA, а затем для создания DFA из него, используя алгоритм goto / closure. Теперь вопрос, как мне минимизировать это?…
21 июн '12 в 05:56
0
ответов
Преобразование NFA в регулярное выражение
Я только что написал код для преобразования NFA в регулярные выражения, но проблема в том, что ответ не оптимизирован. Например: c * (a + b) (e) * (e) + c * (a + b) и ответ, данный моим кодом, я хочу знать, есть ли простое решение для минимизации ре…
06 апр '13 в 14:13
1
ответ
Когда машины Тьюринга имеют конечные состояния?
Это может быть глупый вопрос, но когда у машин Тьюринга есть конечные состояния? Я вижу некоторых с конечными состояниями, а некоторых нет, я сейчас немного растерялся.
23 янв '18 в 20:44
1
ответ
Как работает минимизация DFA?
Что-то не так с этими заметками, написанными моим профессором? Насколько D&F; и B&C; эквивалентны? Они не должны быть, потому что функции транзакций дают разные состояния. Если это нормально, и мы заботимся об эквивалентности одного и того же ввода,…
15 фев '16 в 12:56
1
ответ
Сокращения в NFA, питоне
Я пытаюсь создать метод пропуска аббревиатур из одной точки в другую. Я создал NFA с текущими краями EDGES = [ (0, 'h', 1), (1,'a',2), (2,'z', 3), (3,'a',4), (4, 'r', 5), (5, 'd', 6) )] Пример того, что я пытаюсь достичьnrec("h-rd", nfa, 1) должен в…
16 фев '13 в 21:27
0
ответов
Запишите регулярное выражение, которое создает начальный NFA с ровно 13 состояниями, ровно два из которых имеют ровно три входные дуги
У меня есть о ДФА и НФА: Я должен записать регулярное выражение, которое производит начальный NFA с ровно 13 состояниями, ровно два из которых имеют ровно три входные дуги. Как бы это выглядело и с чего мне начать? Я застрял на некоторое время. Спас…
18 фев '19 в 05:34
0
ответов
Затраты времени на создание и запуск NFA против DFA для данного регулярного выражения
Я прохожу прошлые экзамены и постоянно сталкиваюсь с вопросами, на которые я не могу найти ответ в учебниках или в Google, поэтому любая помощь будет высоко ценится. Вопрос, с которым у меня сейчас проблемы, заключается в следующем: Учитывая регуляр…
06 авг '12 в 15:05
1
ответ
Параллельное сопоставление регулярных выражений с NFA против DFA? Какой из них быстрее?
Я читал о NFA и DFA, и кажется, что самый популярный и самый быстрый способ внедрения regex matcher - это создание NFA из regex, преобразование его в DFA, минимизация этого DFA, реализация его на любом языке и использование его. DFA - лучший выбор п…
17 июн '16 в 23:11
3
ответа
Разработка недетерминированных конечных автоматов в C++ (неверный вывод)
Я делаю задание для симуляции недетерминированного конечного автомата, как я объясняю в этом посте. У меня есть этот вход читать из файла tarea4.in: 1 6 8 0 2 2 5 0 0 a 0 1 a 1 1 b 1 2 c 1 3 c 3 4 d 4 4 d 4 5 d 5 aaabcccc aabbbbcdc abbcdddcc acddddd…
16 май '12 в 20:44
0
ответов
Строковый метод доступа заставляет строку быть int C++
Я пытаюсь закодировать NFA в C++, который может распознать строку и определить, принята или отклонена эта строка. У меня есть строковый вход, который будет оцениваться как входящий. Тем не менее, как только я перехожу к нему в функции valuInput() (в…
20 фев '16 в 23:50
1
ответ
Преобразование регулярного выражения в таблицу переходов NFA
Не имеет значения язык, но мне нужно выяснить, как преобразовать регулярное выражение в таблицу NFA. Например, "(ab)* + ba" превращается вT | а | б | ^0 | N | 1 | 21 | 3 | N | N2 | 4 | N | 33 | N | N | N4 | N | 2 | N Если бы кто-нибудь мог помочь на…
26 апр '17 в 22:57
3
ответа
Преобразование NFA в DFA
Когда мы конвертируем из nfa в dfa, может быть результат, подобный изображенному ниже... Мой вопрос: нужно ли писать, что из состояния {4} он переходит в нулевое состояние? Я имею в виду, что без отображения входной символ 1 из {4} совпадает с изобр…
04 июн '12 в 21:06
1
ответ
Как конвертировать (ab u aab u aba)* в NFA?
(ab u aab u aba)* Я сделал это, но я хотел бы получить некоторые отзывы о его правильности: Если это правильно: Можем ли мы упростить (ab u aab u aba)* дальше? Если нет: что я пропустил? РЕДАКТИРОВАТЬ: Кажется, мне не хватает электронных переходов и…
17 окт '11 в 22:38
1
ответ
NFA к теореме Р. Е. Клини
Вот мой НФА: Вот моя попытка. Создать новый начальный и конечный узлы Затем удалите 2-й узел слева, который дает мне Затем удалите 2-й узел справа, который дает мне ab*a Затем удалите 2-й узел слева, который дает мне abb*b Затем удалите 2-й узел спр…
30 янв '13 в 01:13
1
ответ
Реализация NFA для ходов на шахматной доске 3X3
У меня есть следующая шахматная доска: Каждый квадрат - это состояние. Начальное состояние - "а". Учитывая пользовательский ввод цвета квадратов, куда он хочет переместиться, программе необходимо найти все возможные маршруты в соответствии с этим вв…
04 ноя '17 в 05:14
0
ответов
Реализация алгоритма Бжозовского
Я работаю над реализацией алгоритма Бжозовского в C++. У меня нет проблем, чтобы понять этот алгоритм, но я понятия не имею, как написать весь материал на C++. У меня есть идея, как это должно работать, но у меня нет навыков программирования. Может …
09 июн '13 в 18:53