Вопросы по теме 'finite-automata'
Теория вычислений - демонстрация того, что язык является регулярным
Я просматриваю некоторые заметки к моему курсу по теории вычислений, и я немного застрял на показе следующего утверждения, и я надеялся, что кто-нибудь может помочь мне с объяснением :)
Пусть A - регулярный язык. Язык B = {ab | a существует в A,...
1324 просмотров
schedule
06.06.2023
Насколько полезна полнота по Тьюрингу? завершены ли нейронные сети по Тьюрингу?
Читая некоторые статьи о полноте по Тьюрингу рекуррентных нейронных сетей (например: вычислимость по Тьюрингу с нейронными сетями, Hava T. Siegelmann и Eduardo D. Sontag, 1991), у меня возникло ощущение, что приведенное там доказательство не совсем...
11424 просмотров
schedule
08.11.2023
ЦФА Левенштейна в .NET
Добрый день,
Кто-нибудь знает о готовой реализации DFA Левенштейна ( детерминированные конечные автоматы ) в .NET (или легко переводимой на нее)? У меня есть очень большой словарь с более чем 160000 различных слов, и я хочу, учитывая начальное...
1815 просмотров
schedule
22.07.2023
Существует ли эффективный алгоритм определения того, является ли язык, принятый одним NFA, надмножеством языка, принятого другим?
Учитывая два недетерминированных конечных автомата M1 и M2 , существует ли эффективный алгоритм для определения того, является ли язык, принятый M1 , надмножеством принятого языка Автор M2 ?
500 просмотров
schedule
23.01.2023
Два входа в автоцикл, детерминированный или недетерминированный конечный автомат?
В Википедии говорится, что автоматизация детерминированного состояния «производит уникальные вычисления (или запуск) автомата для каждой входной строки».
Я всегда понимал это как единственный возможный путь для вычисления любой уникальной строки....
1934 просмотров
schedule
18.04.2023
Есть ли связь между DFA и Loop, NFA и рекурсией?
Я слышал, что DFA можно моделировать с помощью Loop, а NFA можно моделировать рекурсивным методом. Я не понимаю, как это работает. Может ли кто-нибудь привести мне пример?
924 просмотров
schedule
25.05.2022
Разрешимость FA с тремя состояниями
Я пытаюсь выяснить, как описать пятьдесят шесть строк, чтобы проверить, имеет ли FA с тремя состояниями над алфавитом {a b} конечный язык.
Число пятьдесят шесть исходит из теоремы, которая гласит, что если машина имеет N состояний, а алфавит...
124 просмотров
schedule
25.05.2022
Является ли данный контекстно-свободный язык регулярным
Разрешимо ли:
Данная грамматика свободна от контекста?
Данный рекурсивный язык свободен от контекста?
Данный контекстно-свободный язык является регулярным?
625 просмотров
schedule
16.04.2022
Как разработать DFA для следующего языка?
Как мне разработать DFA для:
Σ = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
набор десятичных цифр.
L = {w| The decimal number represented by w leaves an odd remainder when divided by seven.}
Пока что я (вручную) нарисовал семь состояний (q0 -...
847 просмотров
schedule
29.06.2022
Кратчайшее регулярное выражение для двоичного числа с четным числом нулей или нечетным числом единиц
Напишите выражение, содержащее четное количество нулей или нечетное количество единиц.
Я понял:
1*(01*01*)* + 0*10*(10*10*)*
где первая часть представляет собой четное количество нулей, а вторая часть - нечетное количество единиц.
Однако...
30218 просмотров
schedule
08.10.2022
Машина Тьюринга, принимающая строки с одинаковой начальной и конечной длиной
Мне нужна помощь в создании одноленточной детерминированной машины Тьюринга для этого языка
здесь я не уверен, как определить, какие строки примет ТМ. Как я могу заставить машину принимать строки, где a=c? потому что часть b содержит элементы...
1557 просмотров
schedule
06.10.2022
Инструментальная поддержка изучения автоматов и грамматик
Я изучаю формальные языки и компиляторы, и мне немного сложно все понять. Есть ли инструмент, позволяющий создавать автоматы и грамматики и выполнять над ними операции? Такие операции, как: минимизация автомата по автоматной грамматике, от...
81 просмотров
schedule
28.07.2022
Метаинформация в DAWG/DAFSA
Я хотел бы реализовать структуру данных поиска строк для динамических строк, которая будет поддерживать эффективный поиск и вставку. В настоящее время я использую попытку, но я хотел бы уменьшить объем памяти, если это возможно. Эта статья в...
698 просмотров
schedule
01.05.2023
Как определить, является ли автомат с конечным числом детерминированным?
У меня есть курсовая работа по автоматам, которая действительно беспокоит меня своей сложностью. Сегодня я провел почти 5 часов, не зная, правильно это или нет. Задача состоит в том, чтобы написать Java-код, который будет определять, является ли...
1172 просмотров
schedule
04.01.2023
Каждый регулярный язык конечен | Правда или ложь?
Я пытался решить это с помощью антипримера L=a* as, но это кажется неправильным.
{0, a, aa, ...} связано с количеством строк
какие-либо предложения?
2491 просмотров
schedule
27.04.2022
Регулярное выражение в конечных автоматах
Мне нужно объяснение регулярного выражения:
Все строки {a,b}, не содержащие 2 или более букв a подряд.
87 просмотров
schedule
24.06.2022
Выражение АТД стека с помощью диаграммы конечного автомата
Я пытаюсь использовать диаграмму конечного автомата для представления абстрактного типа данных Stack и изо всех сил пытаюсь найти способ представить неограниченный алфавит. В стеке может быть бесконечное количество элементов, но я не могу рисовать...
165 просмотров
schedule
13.06.2023
Союз языков, принятых FSA, без переходов эпсилон
Я пытался формализовать объединение двух автоматов с конечным состоянием без использования эпсилон-переходов. Я хочу создать новое начальное начальное состояние для новых автоматов и из этого нового начального состояния создать переходы в достижимые...
132 просмотров
schedule
05.02.2023
Нахождение DFA r *, когда r и DFA r были определены
Я хотел бы, чтобы пример этого метода находил DFA r *, когда r и DFA r были определены. А как думать? Я читал учебник, но я не понимаю ясно. Спасибо.
49 просмотров
schedule
09.02.2023
Получение регулярной грамматики для языка, распознаваемого конечными автоматами
У меня возникли проблемы с выводом правильной грамматики для языка, который распознается конечными автоматами. Ключевой проблемой, с которой я столкнулся, является путаница между обычной грамматикой и контекстно-свободной грамматикой. Я не могу...
527 просмотров
schedule
19.06.2022
