Вопросы по теме 'nfa'
Разница между датчиком и NFA
Может ли кто-нибудь сказать мне, чем преобразователь отличается от NFA?
427 просмотров
schedule
09.12.2022
Обычный язык?
У меня вопрос по компилятору.
Определите, является ли {(ab)^n | n >= 0} является обычным языком?
Но я могу нарисовать свою НФА. Но если я воспользуюсь леммой о накачке, то получу противоречащий ответ.
Может кто-нибудь мне помочь ?
708 просмотров
schedule
30.05.2022
Как преобразовать NFA в регулярное выражение
Я знал, что для преобразования регулярного выражения в NFA существует алгоритм.
Но мне было интересно, есть ли алгоритм для преобразования NFA в регулярное выражение. Если есть, то что это?
А если нет, мне также интересно, могут ли все NFA...
13675 просмотров
schedule
19.02.2024
Найдите регулярное выражение для языка на E={a,b}
L = w : (na(w) - nb(w)) по модулю 3 /= 0
Как я могу найти регулярное выражение для этого языка?
Я так понимаю, это значит, что количество А минус количество Б не может быть кратно 3. Значит а - б не может быть 3,6,9,12 и т.д.
Но у меня все...
1566 просмотров
schedule
24.09.2023
Как именно ленивые квантификаторы работают в PCRE?
Немного предыстории: я реализую механизм сопоставления регулярных выражений (NFA), и он должен поддерживать режим совместимости с PCRE (я имею в виду, что он должен захватывать подвыражения с теми же смещениями, что и PCRE).
В PCRE testinput1 есть...
378 просмотров
schedule
14.06.2023
Приостановить поток, пока метод и все потоки внутри не закончат свою работу?
Я новичок в потоках, и мне было интересно, как их использовать для оценки в недетерминированном конечном автомате.
У меня есть метод, который вызывает другой метод:
public bool Evaluate2(string s)
{
accepted = false;
ThreadEval(s,...
4388 просмотров
schedule
13.03.2023
Разработать регулярное выражение или конечные автоматы для языка, состоящего из 01 или 010?
Я пробовал ниже вопрос для проектирования автоматов, но не добился успеха:
Набор строк, состоящий из 01 , повторяющихся один или несколько раз, или 010 , повторяющихся один или несколько раз.
где строка содержит только двоичные символы....
665 просмотров
schedule
01.04.2022
Реализация недетерминированного конечного автомата (NFA)
Я пытаюсь разработать симуляцию, которая выполняет недетерминированный конечный автомат на Java. Первый аргумент командной строки — это текстовый файл, определяющий машину. Второй аргумент — это входная строка. Если он принимает строку, он печатает...
4987 просмотров
schedule
17.08.2022
Невозможно построить NFA с 4 состояниями для определенного регулярного выражения
В упражнении по NFA меня попросили построить NFA с 4 состояниями на основе регулярного выражения (aa|aab)*b. Я пытался построить его сам, но смог найти NFA только с 5 состояниями, что позже подтвердил онлайн-инструмент.
(Я нашел это без (4)...
119 просмотров
schedule
09.12.2022
Конструктор конечных автоматов - Racket Language
Мне нужно создать конструктор конечной машины, который принимает все префиксы языка данной машины. Скажем, язык машины M1 L (M1) = "abba", тогда конструктор должен создать новую машину M2 такую, что L (M2) = {empty, a, ab, abb, abba}
Теперь в...
693 просмотров
schedule
26.03.2022
Построение подмножества DFA из NFA
Я читаю книгу «Принципы, методы и инструменты компиляторов» Альфреда В.Ахо. Конструкция подмножества DFA из NFA имеет следующие операции над состояниями NFA.
e-closure(s)| Set of NFA states reachable from NFA state s on e-transations alone...
1537 просмотров
schedule
20.05.2022
Доказательство языка является регулярным
Пусть Σ — конечный алфавит и L ⊆ Σ — язык. Пусть Σ0 ⊆ Σ. Для каждой строки w = w1 · · · wn ∈ Σ определим res(w, Σ0) = y1 · · · yn, где yi = wi, если wi ∈ Σ0, и yi =, если wi ∈ Σ \ Σ0, для каждый 1 ≤ i ≤ n. (Например, res(абракадабра, {a, b}) =...
306 просмотров
schedule
17.05.2022
Параллельное сопоставление регулярных выражений с NFA и DFA? Какой из них быстрее?
Я читал о NFA и DFA, и кажется, что самый популярный и быстрый способ реализации сопоставления регулярных выражений - это создать NFA из регулярных выражений, преобразовать его в DFA, минимизировать этот DFA, реализовать его на любом языке и...
636 просмотров
schedule
18.04.2023
Пересечение двух регулярных выражений
Спасибо за любую помощь заранее!
Я беру курс автоматов в школе и для жизни не могу решить пересечение двух регулярных выражений. Я посмотрел в Интернете и здесь и обнаружил, что могу создать NFA для обоих языков, дополнить их по отдельности, а...
911 просмотров
schedule
27.05.2022
Сдвинуть автоматы для языка
Я хочу разработать автоматические автоматы для языка
L = { a^i b^j c^k | i = j or k <= j <= 2k}
Решение, предложенное инструктором, показано на следующей диаграмме.
Но меня беспокоит то, что он не обрабатывает строку формы,...
527 просмотров
schedule
17.08.2022
Как механизмы Regex генерируют NFA для регулярных выражений?
На этой вики-странице: https://www.owasp.org/index.php/Regular_expression_Denial_of_Service_-_ReDoS#The_problematic_Regex_na.C3.AFve_algorithm
Вы можете видеть, что для регулярного выражения ^(a+)+$
создается следующий NFA:
Мой...
113 просмотров
schedule
09.06.2022
Преобразуйте это из NFA в DFA
Создайте DFA (с алфавитом {a,b}), эквивалентный следующему NFA:
Мое преобразование показано ниже, но оно кажется неправильным, можете ли вы помочь мне объяснить, почему?
232 просмотров
schedule
18.01.2024
Показано, что пересечение двух языков, принятых NFA, неразрешимо.
У меня проблема с этой проблемой.
Пусть A = {〈N1, N2〉 | N1 и N2 являются НКА и L(N1) ∩ L(N2) = ∅}. Покажите, что A разрешима.
Любая помощь приветствуется.
158 просмотров
schedule
06.08.2022
Преобразовать данный NFA
Вопрос) Σ={a,b} и NFA представлен на следующем рисунке:
Используя процедуру NFA to DFA, преобразуйте данные NFA в DFA.
Используя процедуру сокращения, минимизируйте состояния в DFA
Я сделал таблицу переходов как для nfa, так и для dfa,...
155 просмотров
schedule
27.10.2022
Преобразование NFA для проверки электронной почты в DFA
Может ли кто-нибудь помочь в том, как преобразовать NFA для этой проверки электронной почты в DFA?
Чтобы сделать преобразование, я сначала создал таблицу перехода состояний, а затем может ли кто-нибудь помочь создать DFA?
112 просмотров
schedule
05.08.2022