Описание тега dfa

Вопросы с тегом
DFA - это детерминированный конечный автомат, простая модель вычислений. Это один из способов моделирования обычных языков. Каждый DFA состоит из конечного набора состояний и функции перехода между этими состояниями, описывающей, как состояние машины изменяется в ответ на новый ввод. DFA тесно связаны с регулярными выражениями в том смысле, что их можно преобразовывать друг в друга. Таким образом, DFA часто используются для реализации сопоставителей регулярных выражений.
0 ответов

NFA для базы m не делится на n

Мне дали упражнение найти DFA for base m no divisible by m, Благодаря этой ссылке я узнал, как это сделать, но потом подумал, как бы мы подошли к этому упражнению, если бы оно создавало NFA а затем преобразовать его в DFA, используя метод построения…
23 сен '18 в 07:30
1 ответ

Минимальное количество состояний необходимо?

Определение языка L с алфавитом { a } дается следующим образом L = {ank | k> 0; и n является положительной целочисленной константой} Какое количество состояний требуется в DFA для распознавания L? На мой взгляд, это должно быть k+1, но я не уверен.
13 фев '11 в 14:55
0 ответов

Может ли язык иметь несколько решений в диаграмме dfa?

Что я имею в виду, что может быть несколько разных форм диаграмм одного и того же языка? Можно ли нарисовать несколько решений? Или у каждого языка есть только одно решение в DFA? Я посетил поп-викторину сегодня. Нарисовал решение и перепробовал нес…
12 июл '18 в 06:34
2 ответа

Нужно регулярное выражение для конечных автоматов: четное число 1 и четное число 0

Моя проблема может звучать иначе для вас. Я начинающий, и я изучаю конечные автоматы. Я пытаюсь найти в Интернете регулярное выражение для конечных автоматов данной машины. Может кто-нибудь помочь мне написать "Регулярное выражение для конечных авто…
02 июл '13 в 07:56
2 ответа

Регулярное выражение: сопоставление ',' после нуля или нечетного вхождения двойной кавычки

Я пытаюсь отделить строку из файла CSV без использования анализатора, и все, что мне нужно сделать, это разделить строку на основе запятых с помощью php. Само по себе это довольно просто, если у вас нет запятых на входе, что не так. Я хочу игнориров…
17 янв '12 в 22:26
1 ответ

Инструменты для создания dfa из правил грамматики

Я ищу любой инструмент или программное обеспечение, которое преобразует набор правил в детерминированные конечные автоматы. На самом деле, я разрабатываю стеммер, что-то вроде портера стеммера для английского языка. У меня есть набор правил, которые…
18 ноя '12 в 10:17
1 ответ

Парсер против лексера и XML

Сейчас я читаю об архитектуре компиляторов и синтаксических анализаторов и меня интересует одна вещь... Когда у вас есть XML, XHTML, HTML или любой язык на основе SGML, какова будет роль лексера здесь и какие будут токены? Я читал, что токены похожи…
02 сен '10 в 02:07
1 ответ

Значение комбинированных состояний в DFA

При конвертации и NFA в DFA, иногда государства должны быть объединены. Как в приведенном выше сценарии. Но что на самом деле означает "объединять государства в одно" в реальном сценарии? И какова будет природа комбинации двух вышеупомянутых госуда…
08 ноя '17 в 05:59
1 ответ

Создать синтаксическое дерево из заданных регулярных выражений (для RE в DFA)

Я изучаю теорию автоматов и сталкиваюсь с некоторыми трудностями при конвертации RE непосредственно в DFA. Этот метод требует создания синтаксического дерева из RE. Но я не могу генерировать.Мне дают регулярное выражение, например a*b*(a|b)abc Тепер…
15 ноя '14 в 17:39
3 ответа

Минимизация DFA

У меня есть вопрос о минимизации DFA. Поэтому я использовал очень хорошо известные методы для преобразования регулярного выражения в NFA, а затем для создания DFA из него, используя алгоритм goto / closure. Теперь вопрос, как мне минимизировать это?…
21 июн '12 в 05:56
1 ответ

Когда машины Тьюринга имеют конечные состояния?

Это может быть глупый вопрос, но когда у машин Тьюринга есть конечные состояния? Я вижу некоторых с конечными состояниями, а некоторых нет, я сейчас немного растерялся.
23 янв '18 в 20:44
1 ответ

DFA удалить недопустимые символы

Так что я представляю это DFA: Как это initial(0). final(2). arc(0,a,1). arc(0,b,0). arc(1,a,1). arc(1,b,2). arc(2,a,2). arc(2,b,2). И у меня есть предикат, который анализирует строку и возвращает true, если это приемлемо: transition(X,[A|B]) :- arc…
10 янв '19 в 16:43
5 ответов

Основанные на DFA модули регулярных выражений для Java с Capture

Существуют ли (бесплатные) механизмы регулярных выражений для Java, которые могут компилировать регулярное выражение в DFA и выполнять захват группы при сопоставлении DFA? Я обнаружил dk.brics.automaton и jrexx, которые компилируются в DFA, но ни од…
26 дек '09 в 18:21
4 ответа

DFA не принимает строки

Моя программа должна реализовывать dfa для двоичной строки... dfa - это машина, которая может находиться только в одном состоянии за раз (когда вы вводите строку, машина должна использовать ее и на последнем шаге она должна достичь конечное состояни…
15 июн '14 в 18:07
1 ответ

Как работает минимизация DFA?

Что-то не так с этими заметками, написанными моим профессором? Насколько D&F; и B&C; эквивалентны? Они не должны быть, потому что функции транзакций дают разные состояния. Если это нормально, и мы заботимся об эквивалентности одного и того же ввода,…
15 фев '16 в 12:56
0 ответов

Запишите регулярное выражение, которое создает начальный NFA с ровно 13 состояниями, ровно два из которых имеют ровно три входные дуги

У меня есть о ДФА и НФА: Я должен записать регулярное выражение, которое производит начальный NFA с ровно 13 состояниями, ровно два из которых имеют ровно три входные дуги. Как бы это выглядело и с чего мне начать? Я застрял на некоторое время. Спас…
18 фев '19 в 05:34
3 ответа

Как я могу доказать, что этот язык является регулярным?

Я пытаюсь доказать, если этот язык: L = {w = {0,1} * | #0(w)% 3 = 0} (число 0 делится на 3) регулярно пользуется леммой прокачки, но я не могу найти способ сделать это. Все остальные примеры, которые я получил, имеют простую форму или, скажем, более…
17 дек '15 в 18:08
0 ответов

Детерминант конечных автоматов (JFLAP) с использованием числа с плавающей запятой (теория языка и автоматов)

Нарисуйте DFA, который будет числом с плавающей запятой, в следующем формате: mts E Eks, где mts: mantisa integer, круглые сферы не более 2 цифр. Примеры: -2,5 Е 03, 2,56 Е 12 У меня возникли проблемы с описанием dfa, который распознает числа с плав…
02 окт '17 в 14:19
1 ответ

Параллельное сопоставление регулярных выражений с NFA против DFA? Какой из них быстрее?

Я читал о NFA и DFA, и кажется, что самый популярный и самый быстрый способ внедрения regex matcher - это создание NFA из regex, преобразование его в DFA, минимизация этого DFA, реализация его на любом языке и использование его. DFA - лучший выбор п…
17 июн '16 в 23:11
1 ответ

Как получить пересечение DFA?

Как объединить два dfa, используя метод пересечения?
22 июн '10 в 19:30