Вопросы по теме 'finite-automata'
Включает ли C # конечные автоматы?
Недавно я прочитал о библиотеке boost::statechart (конечных автоматах), и мне понравилась эта концепция.
Есть ли в C # аналогичный механизм? Или это можно реализовать с помощью определенного шаблона проектирования?
36802 просмотров
schedule
07.02.2023
Lex и Yacc для конечных автоматов
Я хочу разработать инструмент для построения графа переходов любого конечного автомата с учетом его таблицы переходов, начального состояния и конечного состояния, используя Lex и Yacc . Инструмент также должен предоставлять средство для проверки...
1366 просмотров
schedule
29.06.2023
Проверка пересечения двух обычных языков
Я хочу проверить, есть ли у двух языков общая строка. Оба эти языка относятся к подмножеству обычных языков, описанных ниже, и мне нужно только знать, существует ли строка в обоих языках, а не создавать пример строки.
Язык определяется строкой в...
1756 просмотров
schedule
07.11.2022
Каковы теоретические последствия неограниченного просмотра назад?
Большинство языков допускают просмотр назад с фиксированной или конечной длиной. Заметным исключением является .NET, который позволяет использовать оператор *.
Однако регулярные выражения .NET уже могут распознавать сбалансированные круглые скобки...
173 просмотров
schedule
06.09.2022
Необходимо минимальное количество состояний?
Определение языка L с алфавитом { a } дается следующим образом
L = { a nk | к > 0; и n — положительная целочисленная константа }
Какое количество состояний необходимо в DFA для распознавания L ?
На мой взгляд, должно быть k+1, но я...
3792 просмотров
schedule
03.08.2023
Минимизация конечного автомата
Я пытаюсь минимизировать этот DFA: http://img145.imageshack.us/img145/3006/dfac.png
Вот мой свернутый DFA: http://img195.imageshack.us/img195/4131/mdfa.png
Я прав? Спасибо
P.S. Это домашнее задание. Нам разрешено обсуждать домашнее...
391 просмотров
schedule
12.06.2023
Преимущества/недостатки NFA по сравнению с DFA и наоборот
Каковы относительные плюсы и минусы DFA и NFA по сравнению друг с другом?
Я знаю, что DFA легче реализовать, чем NFA, и что NFA медленнее достигают состояния принятия, чем DFA, но есть ли какие-либо другие явные, хорошо известные...
14913 просмотров
schedule
18.11.2022
моделировать детерминированный стек-автомат (DAS) в С++
Я читал упражнение UVA, которое мне нужно для имитации детерминированного автомата стека, чтобы увидеть, принимаются или нет DSA определенные строки для данной записи в следующем формате:
В первой строке ввода будет целое число C, указывающее...
590 просмотров
schedule
08.04.2022
Конечный автомат для встроенных устройств
Я сделал несколько меню, используя FSM, но с ОЧЕНЬ неуклюжим интерфейсом. Я взял годичный перерыв в программировании, чтобы облегчить переезд, и только сегодня вечером переписал свой старый код FSM.
Его можно увидеть ЗДЕСЬ
Проблема с моим...
539 просмотров
schedule
13.02.2023
Нужна помощь в построении детерминированного конечного автомата?
Каковы правила построения детерминированного конечного автомата в виде диаграммы? Мой профессор объяснил на примерах, но я не совсем уверен, каким правилам должны следовать все диаграммы. Любая помощь приветствуется, спасибо!
1950 просмотров
schedule
15.04.2022
Как использовать конструкцию пересечения для формирования DFA?
Я делаю домашнее задание для своего класса теории вычислений и немного запутался, как объединить 2 DFA. В книге говорится, что для этого используется «конструкция пересечения», но я не уверен, что это такое. Вот 2 примера:
39106 просмотров
schedule
16.10.2022
Эквивалентности регулярных выражений
Верна ли следующая эквивалентность регулярного выражения? Почему или почему нет?
(ab)* u (aba)* = (ab u aba)*
* = звезда Клини
u=Союз (Теория множеств)
460 просмотров
schedule
18.11.2022
Как реализовать привязку цветной сети Петри в Java?
Я реализую цветную сеть Петри на Java. Это что-то вроде конечного автомата. Проблема в том, что я не знаю, как реализовать "привязку". Другими словами, цвета должны быть назначены местам, а выражения дуг должны быть назначены дугам. После...
601 просмотров
schedule
15.03.2023
Может ли DFA иметь переходы эпсилон/лямбда?
Ничего утвердительного по этому поводу найти не могу. И NFA с любым эпсилон-переходом является эпсилон-NFA? Спасибо.
24534 просмотров
schedule
21.07.2022
Странное закрытие пустой строки dfa
http://imgur.com/oQ6Yv
Рассматриваемое закрытие - это закрытие этого конечного состояния, я думал, что это будет то же самое, что и закрытие первого состояния, поскольку в них обоих отсутствует переход из соответствующих состояний в пустой...
159 просмотров
schedule
02.03.2023
Сокращения в NFA, python
Я пытаюсь создать метод, в котором аббревиатуры перескакивали с одной точки на другую.
Я создал NFA с текущими краями
EDGES = [
(0, 'h', 1),
(1,'a',2),
(2,'z', 3),
(3,'a',4),
(4, 'r', 5),
(5, 'd', 6)
)]
Пример того, что я пытаюсь...
447 просмотров
schedule
16.05.2022
В чем преимущество минимизации конечных автоматов?
Минимизация дискретного конечного автомата — это стандартная задача в информатике. Каковы преимущества минимизации конечных автоматов? Это просто академическая проблема?
986 просмотров
schedule
22.05.2023
Написание грамматики GNF для CFL
Здравствуйте, я хотел бы задать вам этот вопрос.
Я должен был вычислить (вручную) грамматику в нормальной форме Грейбаха, которая генерирует язык
L = {a i b j c k | i + j = 2k and k >= 1}
Я действительно понятия не имею,. Кто-нибудь...
1802 просмотров
schedule
24.06.2023
Конечность регулярного языка
Все мы знаем, что (a + b)* — это обычный язык, содержащий только символы a и b . Но (a + b)* — это строка бесконечной длины, и она регулярна, поскольку мы можем построить конечные автоматы, поэтому она должна быть конечной.
Кто-нибудь может...
3032 просмотров
schedule
17.12.2022
Оцените количество состояний в DFA (пересечение)
У меня возникли проблемы с пониманием того, как оценить количество состояний на пересечении двух DFA (M1 и M2, которые имеют n и k состояний). Я не хочу строить настоящий DFA, а хочу понять, сколько состояний даст пересечение. Например, объединение...
1005 просмотров
schedule
01.10.2022