Вопросы по теме 'nfa'
Если язык (L) распознается NFA с n состояниями, может ли он также распознаваться DFA с не более чем 2 ^ n состояниями?
Я так думаю, потому что верхней границей будет 2 ^ n, и, учитывая, что это обе конечные машины, пересечение как для NFA с n состояниями, так и для DFA с 2 ^ n или меньше состояний будет действительным.
Я ошибаюсь здесь?
889 просмотров
schedule
28.08.2022
Существует ли эффективный алгоритм определения того, является ли язык, принятый одним NFA, надмножеством языка, принятого другим?
Учитывая два недетерминированных конечных автомата M1 и M2 , существует ли эффективный алгоритм для определения того, является ли язык, принятый M1 , надмножеством принятого языка Автор M2 ?
500 просмотров
schedule
23.01.2023
Как я могу доказать, является ли этот язык правильным или нет?
Как я могу доказать, является ли этот язык правильным или нет?
L = {a n b n : n1} union {a n b n+2 : n1}
2954 просмотров
schedule
27.08.2022
Разработка недетерминированного конечного автомата на С++ (неверный вывод)
Я выполняю задание для имитации недетерминированного конечного автомата, как я объясняю в этом post . У меня есть этот ввод, прочитанный из файла 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...
15082 просмотров
schedule
20.07.2022
Почему моя программа на С++ дает сбой при определенном вводе?
В течение нескольких дней я пытаюсь сделать программу для имитации недетерминированного конечного автомата (NFA), точнее, распознавателя строк. После нескольких неудач, благодаря пользователю Konrad Rudolph , я смог реализовать решение на основе...
771 просмотров
schedule
09.02.2023
Проектирование nfa, которое принимает пару строк
Мне нужна помощь в разработке nfa, который принимает слова «привет», «привет, мир» и «остаться вместе», алфавит включает английский алфавит, цифры и символы. Мне нужна помощь, чтобы начать. У кого-нибудь есть предложения?
458 просмотров
schedule
21.04.2024
Диапазоны и группы регулярных выражений для DFA реализованы в виде таблицы
В настоящее время я играю с преобразованием из регулярного выражения (без групп захвата, без возврата) в DFA, управляемый таблицей. Я реализовал это, создав NFA из регулярного выражения, а затем преобразовав NFA в DFA. В настоящее время я...
139 просмотров
schedule
02.02.2023
Получить пересечение двух NFA
Итак, у меня есть проблема, когда мне нужно найти пересечение двух NFA, и я не нахожу решения. Итак, у вас есть два автомата m1 и m2 с m1=(Q1, Σ1, ∆1, q1, F1) и m2=(Q2, Σ2, ∆2, q2, F2).
Я думаю, что Q формируется комбинацией состояний Q1 и Q2, так...
1135 просмотров
schedule
07.07.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
Как представить переходы NFA в Python?
Мне нужно реализовать следующий NFA:
Я представляю каждое состояние с помощью функций, но у меня возникают проблемы с получением всех возможных путей с учетом входных данных.
Например, при вводе «bb» у меня должен быть следующий вывод:...
1022 просмотров
schedule
29.06.2023
Процедура конечного автомата
Мне нужно разработать эффективную процедуру принятия решения, чтобы определить, является ли язык, принятый недетерминированным конечным автоматом, пустым.
Я знаю, что машина не принимает строку, если нет пути от начального состояния к конечному...
63 просмотров
schedule
07.04.2022
NFA для алфавитов в матричной форме
Я хочу помочь с моим заданием. Я могу понять, что это не то место, где вы найдете кого-то, кто сделает вашу домашнюю работу, поэтому я также пробовал другие сайты, такие как CHEGG, с той же информацией об учетной записи (говорю вам, чтобы это не...
66 просмотров
schedule
12.04.2023
Проверка модели: неверные префиксы с использованием NFA
Мы используем NFA для моделирования BadPrefixes для свойства безопасности. Я хочу понять для данного свойства безопасности, как моделировать NFA.
Следующие изображения приведены для справки.
Например, для свойства безопасности...
232 просмотров
schedule
29.06.2022
Вставка обычного языка в другой обычный язык
Пусть L1 и L2 будут обычными языками в алфавите {a,b} . Мы определяем язык L3 следующим образом:
L3 = {pqr | pr ∈ L1, q ∈ L2}
L3 получается путем вставки строки из L2 внутрь строки из L1 . Является ли язык L3 по-прежнему...
67 просмотров
schedule
31.05.2023
Как нарисовать DFA языка A={w | Каждая четная позиция w имеет символ 0}?
Мне нужно нарисовать DFA для машины. Машина принимает язык А.
Язык А={ш | Каждая четная позиция w имеет символ 0} и Σ = {0,1}.
Я нарисовал DFA. Не уверен, что это правильно.
Вот мой DFA, DFA [рисунок]
Я хочу знать, правильно это или нет....
528 просмотров
schedule
17.03.2023
Почему эта вспомогательная функция выдает ошибку несвязанного значения?
У меня есть вспомогательная функция, которая выглядит следующим образом:
let rec helper2 nfa l symb res =
match l with
| [] -> res
| h::t -> res@(transitions nfa.trans symb h) in
helper2 nfa t...
41 просмотров
schedule
28.03.2023
