Описание тега finite-automata

Вопросы с тегом
Конечный автомат (FA) - это математическое описание алгоритма, способного анализировать регулярные языки. FA не имеют внешней памяти и, как таковые, могут учитывать только фиксированное количество предыдущих символов при обработке строк. Детерминированный FA (DFA) - это тот, для которого существует только один законный переход между состояниями; недетерминированные FA могут быть преобразованы в эквивалентные DFA. FA- самые слабые из общепринятых автоматов.
1 ответ

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

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

Определение "DFA для языка"

Я только начал изучать теорию вычислений в этом семестре и немного смутился из-за фразы "DFA для языка". Если его попросили построить DFA для некоторого набора двоичных строк L, значит ли это найти DFA M с L(M)=L или просто $L(M)\supset L$?
09 фев '17 в 15:06
1 ответ

Разрешимость трех государственных FA

Я пытаюсь выяснить, как описать пятьдесят шесть строк, чтобы проверить, имеет ли FA из трех состояний над алфавитом {a b} конечный язык. Число пятьдесят шесть происходит из теоремы, которая гласит, что если машина имеет N состояний, а алфавит состои…
08 окт '12 в 18:59
2 ответа

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

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

Что вы делаете, когда доказываете, что язык решаем?

Что вы делаете, когда доказываете, что язык решаем?
24 окт '10 в 14:56
2 ответа

Это правильный график NFA?

Задача: Построить NFA из заданного регулярного выражения. Я решил перенести некоторые из моих старых программ на GitHub. Конкретно проблемы, касающиеся теории формальных языков. После тестирования кода у меня был такой результат, и я не могу точно с…
07 окт '18 в 14:10
1 ответ

Является ли данный контекстно-свободный язык регулярным

Решаемо ли: Данная грамматика не зависит от контекста? Данный рекурсивный язык не зависит от контекста? Данный контекстно-свободный язык является регулярным?
10 дек '12 в 18:08
3 ответа

Как конвертировать NFA/DFA в Java?

У меня есть сценарий, в котором я разработал NFA и, используя JFLAP, преобразовал его в DFA. Мне нужно знать, как закодировать это в Java? В основном, как реализовать эти переходы состояний в Java. Я видел несколько примеров, которые делают это с по…
14 окт '11 в 14:00
1 ответ

Конечные автоматы, автоматы Pushdown и примеры машин Тьюринга

Я ищу хороший источник примеров конечных автоматов, автоматов раскрытия и задач машины Тьюринга (для решения вручную, вручную). Я искал вокруг, но не нашел ничего особенного, поэтому мне интересно, есть ли у кого-нибудь хорошие примеры. Заранее спас…
28 авг '12 в 17:30
3 ответа

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

У меня был этот вопрос на экзамене в конце семестра, к сожалению, я не мог решить его и пробовал несколько дней, но не повезло. Условие - для каждой подстроки длины 4 в строке длины n напишите RE, чтобы форсировать правило - должно быть ровно три ед…
07 фев '17 в 10:54
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
1 ответ

Как создать преобразователь конечного состояния путем составления грамматики?

Я использую библиотеку OpenFST и хотел бы разработать преобразователи конечного состояния (FST) на более высоком уровне, описывая грамматику с помощью формы Бэкуса-Наура (BNF). Кто-нибудь был в состоянии скомпилировать грамматики BNF в OpenFST-потре…
24 мар '15 в 14:43
1 ответ

Реагирует ли конечный автомат на роль маршрутизатора?

Я обнаружил конечные автоматы в качестве альтернативы управлению состоянием пользовательского интерфейса в реактивном приложении. Я думаю, что они превосходны, но я немного озадачен тем, как я должен их использовать. Должен ли я создавать конечный а…
08 фев '18 в 04:34
3 ответа

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

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

Сокращение или устранение дублирующихся записей массива

Я хотел бы исключить или радикально сократить записи константного массива для поиска, который включает наборы констант или следующее состояние. Возможно, это очень просто сделать, я просто не знаю, какую структуру использовать. Я пишу встроенный C-к…
16 фев '16 в 19:28
2 ответа

Проверка строки DFA

У меня есть программа, которая просто принимает все состояния как набор состояний в качестве входных данных. И затем следующий вход, который берется, является начальным состоянием среди набора состояний и затем набором конечных состояний. Следующий …
20 сен '11 в 09:45
1 ответ

Какие есть двигатели для конечных автоматов общего назначения?

Требования следующие: основные функции автоматизации: состояния, события, правила гибкость (интеграция с внешними языковыми инструментами для анализа, классификации, поиска) декларативные, изменения без перекомпиляции [опционально] возможности рандо…
12 апр '16 в 09:43
4 ответа

Как мне построить этот конечный автомат?

Я учусь на тест дискретной математики, и я нашел это упражнение, которое я не могу понять. "Построить базовый конечный автомат (DFA,NFA,NFA-лямбда) для языка в алфавите Sigma = {0,1,2}, где сумма элементов в строке четная И эта сумма больше 3" Я поп…
19 май '09 в 22:50
1 ответ

Диаграммы конечных автоматов

Я хочу преобразовать следующую NFSA (см. Изображение ниже) в DFSA. Сначала позвольте мне объяснить, как я обычно это делаю: Я присоединяюсь к состояниям, чтобы создать новое начальное состояние (старое начальное состояние, которое здесь равно 1, и с…
29 окт '14 в 11:17
1 ответ

Regex (a?)* Не экспоненциально?

В настоящее время я смотрю на проблему регулярных выражений, которые могут в конечном итоге работать в экспоненциальном времени при сопоставлении с определенным входом, например оба (a*)* а также (a|a)* потенциально может иметь " катастрофическое во…
26 авг '12 в 23:53