Вопросы по теме 'dfa'
Парсер против лексера и XML
Я сейчас читаю об архитектуре компиляторов и парсеров, и меня интересует одна вещь ... Когда у вас есть XML, XHTML, HTML или любой язык на основе SGML, какова будет роль лексера а какие бы токены были?
Я читал, что токены похожи на слова ,...
3300 просмотров
schedule
05.08.2022
Структура данных для представления DFA
Мне было интересно, какая структура данных будет лучшей для представления DFA?
Я рассматриваю преобразование регулярного выражения в DFA и делаю эту конкретную функциональность библиотекой на Java.
Главное, что каждый объект в регулярном...
2546 просмотров
schedule
23.06.2022
Реализация NFA/DFA на C#
Кто-нибудь знает о какой-либо хорошей реализации NFA и DFA на С#, возможно, реализующей также преобразования между ними? Я хотел бы иметь возможность построить NFA, а затем автоматически преобразовать его в DFA, но без необходимости писать...
16585 просмотров
schedule
08.10.2022
Компромиссы временной сложности nfa против dfa
Я ищу обсуждение того, что лучше использовать и при каких обстоятельствах в компиляторе nfa или dfa. каковы компромиссы временной сложности при моделировании nfa и dfa и какой из них более подходит при каких обстоятельствах в компиляторе??
4565 просмотров
schedule
29.12.2023
Необходимо минимальное количество состояний?
Определение языка L с алфавитом { a } дается следующим образом
L = { a nk | к > 0; и n — положительная целочисленная константа }
Какое количество состояний необходимо в DFA для распознавания L ?
На мой взгляд, должно быть k+1, но я...
3792 просмотров
schedule
03.08.2023
Преимущества/недостатки NFA по сравнению с DFA и наоборот
Каковы относительные плюсы и минусы DFA и NFA по сравнению друг с другом?
Я знаю, что DFA легче реализовать, чем NFA, и что NFA медленнее достигают состояния принятия, чем DFA, но есть ли какие-либо другие явные, хорошо известные...
14913 просмотров
schedule
18.11.2022
Могу ли я использовать DFA для отслеживания строк определенных языков?
Обычно DFA используются для проверки того, присутствует ли данная строка на определенном языке. например, _ab1c присутствует в языке переменных в C.
Что я делаю? Но, как указано в этот вопрос , я использую DFA для отслеживания всех комментариев,...
430 просмотров
schedule
10.03.2023
Является ли язык L = {s ∈ (0 + 1)* | d(s) mod 5 =2 и d(s) mod 7 !=4 } обычный?
При чтении книги у меня возникло это сомнение.
В нем упоминается, что
L = {s ∈ (0+1)* | n0(s) mod 7 = n1(s) mod5 =0} является регулярным, где n0(s) = количество нулей в s и n1(s) = количество 1 в s
Далее упоминается, что
L = {s ∈ (0 + 1)*...
972 просмотров
schedule
22.08.2022
Можем ли мы использовать DFA для синтаксического анализа обычного языка, указанного контекстно-свободной грамматикой, и создания дерева синтаксического анализа?
Как мы знаем, DFA можно использовать для проверки строк на обычном языке.
Пример 1. L=ac(b)*bcb|ad(b)*bb. Строка «acbbbbcb» может быть проверена DFA как правильная.
Кроме того, иногда обычный язык может быть выражен с помощью CFG.
Пример 2....
891 просмотров
schedule
25.02.2024
Может ли DFA иметь переходы эпсилон/лямбда?
Ничего утвердительного по этому поводу найти не могу. И NFA с любым эпсилон-переходом является эпсилон-NFA? Спасибо.
24534 просмотров
schedule
21.07.2022
Детерминистический конечный автомат против детерминированного автомата выталкивания
Мне было интересно, может ли кто-нибудь дать мне простое объяснение взаимосвязи между этими двумя терминами, так как меня очень смущает терминология.
4815 просмотров
schedule
06.06.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
Определение количества состояний в DFA
Для Σ = {a,b,c,d,e,...,z} рассмотрим множество L слов w таких, что последний символ w не встречался ранее. Например, слова «яблоко», «гугл», «к» и «ε» находятся в L, а слова «картофель» и «питание» — нет в L. Предположим, мы хотим построить DFA для...
243 просмотров
schedule
17.04.2022
Оцените количество состояний в DFA (пересечение)
У меня возникли проблемы с пониманием того, как оценить количество состояний на пересечении двух DFA (M1 и M2, которые имеют n и k состояний). Я не хочу строить настоящий DFA, а хочу понять, сколько состояний даст пересечение. Например, объединение...
1005 просмотров
schedule
01.10.2022
Теория автоматов: преобразование контекстно-свободной грамматики в DFA
Как преобразовать контекстно-свободную грамматику в DFA? Это легко сделать, если у нас есть переходы типа A->a B. Но когда у нас есть переходы типа A->a B c. Тогда как мы должны представить его как DFA
10600 просмотров
schedule
24.06.2023
Как нарисовать DFA (или NFA) из простого оператора?
Мне дается простое утверждение: построить DFA над alphabet {0, 1} , который принимает all the strings that end in 101 ?
Мой вопрос заключается в том, каковы будут шаги по его разработке? Или разработайте NFA, потому что тогда я буду знать...
9908 просмотров
schedule
28.09.2023
Ошибка конструктора DFA, что делать для действительного объявления?
Я должен записать этот проект, в котором я должен сделать DFA. Мне трудно понять, как именно написать мой конструктор, чтобы не получить следующую ошибку no matching function for call to 'DFA::DFA(int&, char [2], char [4][2], char&, char...
135 просмотров
schedule
12.08.2022
Характеристики производительности неминимального DFA
О производительности алгоритмов минимизации DFA написано много. Это расстраивает мое гугловское фу, потому что это не то, что я ищу.
Можем ли мы вообще что-нибудь сказать о характеристиках производительности неминимального ЦКА? Моя интуиция...
228 просмотров
schedule
23.10.2022
DFA :- все строки, в которых каждый блок из пяти последовательных символов содержит не менее двух нулей
Я хочу построить DFA для языка: набор всех строк, таких что каждый блок из пяти последовательных символов содержит не менее двух нулей. Как вести учет последних 5 записей. Короче как решить такую проблему. Я получил диаграмму DFA в Интернете, но...
12581 просмотров
schedule
09.08.2022
Преобразование регулярного выражения в DFA
Я пытался преобразовать регулярное выражение
к недетерминированному конечному автомату (NFA), сначала используя конструкцию Томпсона, что дает:
, что выглядит правильно.
Затем я использую построение подмножества для создания DFA из...
1922 просмотров
schedule
10.06.2024
