Публикации по теме 'automata'
Механическое программирование в древние времена
Как давно существует программирование? Программирование началось только с появлением ЭВМ? Или программирование имеет более древнее происхождение? А что же сами компьютеры… вдруг они возникли из «исторического небытия»?
Ноэль Шарки, профессор искусственного интеллекта и робототехники в Шеффилдском университете, изучил работу Герона Александрийского Peri Automatopoietikes (I век н.э.), в которой он описывает, как строит автоматические театры:
После того, как я внимательно прочитал..
Введение в теорию вычислений
Информатика существует уже почти семь десятилетий, и, конечно же, поначалу речь шла не о языках программирования. есть очень важная ветвь компьютерной науки, называемая теорией вычислений, которую я вам представлю, чтобы понять, как компьютеры и, в более общем смысле, «машины» изучались математиками и учеными-компьютерщиками. более конкретно, я представлю теорию автоматов (также известных как абстрактные машины) и формальный язык. Я собираюсь дать вам не подробное, но интуитивное понимание..
Алгоритм CYK
В этой практике речь идет о вычислении алгоритма CYK с учетом грамматики на рисунке 1.
Для вычисления алгоритма CYK грамматика должна быть в нормальной форме Хомского (CNF), как показано в таблице 1, на начальном этапе грамматика очищается, на первом этапе заменяются терминалы, а на втором этапе выполняется расщепление. между терминалом и генератором.
Рассмотрим следующий случай для CFG со словом w=lxt. В этом случае слово является частью языка, заданного грамматикой. S -> BD..
Вопросы по теме 'automata'
Как я могу построить грамматику, которая генерирует этот язык?
Я изучаю тест конечных автоматов и грамматик, и я застрял с этим вопросом:
Construct a grammar that generates L:
L = {a^n b^m c^m+n|n>=0, m>=0}
Я считаю, что мои постановки должны идти по этому пути:
S->aA | aB
B->bB |...
14701 просмотров
schedule
28.10.2022
Использование конечных автоматов в качестве ключей к контейнеру
У меня есть проблема, когда мне действительно нужно иметь возможность использовать конечные автоматы в качестве ключей к ассоциативному контейнеру. Каждый ключ должен фактически представлять класс эквивалентности автоматов, так что при поиске я найду...
1012 просмотров
schedule
15.05.2023
Если язык (L) распознается NFA с n состояниями, может ли он также распознаваться DFA с не более чем 2 ^ n состояниями?
Я так думаю, потому что верхней границей будет 2 ^ n, и, учитывая, что это обе конечные машины, пересечение как для NFA с n состояниями, так и для DFA с 2 ^ n или меньше состояний будет действительным.
Я ошибаюсь здесь?
889 просмотров
schedule
28.08.2022
ЦФА Левенштейна в .NET
Добрый день,
Кто-нибудь знает о готовой реализации DFA Левенштейна ( детерминированные конечные автоматы ) в .NET (или легко переводимой на нее)? У меня есть очень большой словарь с более чем 160000 различных слов, и я хочу, учитывая начальное...
1815 просмотров
schedule
22.07.2023
За что я должен отдавать предпочтение? (количество состояний) или (модульность‹-›читабельность)?
Как я уже говорил в этом вопросе , я использую DFA для отслеживания всех комментариев, строк и т. д. И я закончил этот DFA с 11 состояниями.
Теперь я собираюсь написать DFA для распознавания ключевых слов в java.
Идея:
Изначально pos=0....
79 просмотров
schedule
12.12.2022
доказывая, что язык формы 0 ^ n, где n простое число, не является ни регулярным, ни контекстно-зависимым
Я думаю над этим довольно долго, но так и не смог далеко продвинуться в этом. Первый шаг прост, учитывая любой язык формы o ^ M, где M - простое число, большее, чем то, что дал наш оппонент (скажем, n). Я не могу понять, как мы можем отсюда доказать,...
2168 просмотров
schedule
01.05.2022
Отладка или планирование большого конечного автомата?
Я пытаюсь отладить кусок кода, который в основном представляет собой простой конечный автомат с 16 состояниями, хотя в некоторых случаях переходы не очень просты (данные, с которыми работают изменения состояния, составляют около 200 байт данных в паре...
312 просмотров
schedule
09.11.2022
Проектирование nfa, которое принимает пару строк
Мне нужна помощь в разработке nfa, который принимает слова «привет», «привет, мир» и «остаться вместе», алфавит включает английский алфавит, цифры и символы. Мне нужна помощь, чтобы начать. У кого-нибудь есть предложения?
458 просмотров
schedule
21.04.2024
КОНЕЧНЫЕ автоматы для уточнения регулярных выражений
Вы можете проверить это: https://dl.dropbox.com/u/25439537/finite%20automata.png
Это проверенное домашнее задание, так что не волнуйтесь. Я просто хочу уточнить, правильный мой ответ или нет, потому что он отмечен моим учителем как неправильный....
322 просмотров
schedule
24.05.2023
Что такое «длина накачки» в лемме о накачке?
Я пытаюсь понять, что это за «магическое» число «n», которое используется во всех приложениях леммы «Насос». После нескольких часов изучения этой темы я зашел на следующий веб-сайт: http://elvis.rowan.edu/~nlt/TheoryNotes/PumpingLemma.pdf
Здесь...
13943 просмотров
schedule
14.07.2023
Как разработать 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
Как рекурсивно выполнить упражнение "Странная планета на автоматах"?
Основная идея этого состоит в том, что на планете есть три различных вида видов, только два из трех видов могут собраться вместе, чтобы произвести потомство, и в результате этот вид умирает, а рождаются два новых объекта третьего вида, ибо Например,...
190 просмотров
schedule
13.07.2022
Инструментальная поддержка изучения автоматов и грамматик
Я изучаю формальные языки и компиляторы, и мне немного сложно все понять. Есть ли инструмент, позволяющий создавать автоматы и грамматики и выполнять над ними операции? Такие операции, как: минимизация автомата по автоматной грамматике, от...
81 просмотров
schedule
28.07.2022
Грамматика BNF для набора правил
у меня проблема
(a) Дайте грамматику, используя правила BNF, для построения программы на языке "безмозглый". Безмозглая программа должна следовать правилам: программа должна начинаться и заканчиваться словом «endstart». В языке есть три типа...
895 просмотров
schedule
22.05.2022
Лемма о накачке на контекстно-свободном языке
Для языка {a ^ 2 ^ n | п> = 0}
Я понимаю, что сначала выбирается какое-то k, а затем z = uvwxy такое, что vx! = Epsilon и # (vwx) ‹= k, но я не могу придумать ни одного i, которое доказывает, что этот язык не является контекстно-свободным.
56 просмотров
schedule
01.06.2023
Как определить, является ли автомат с конечным числом детерминированным?
У меня есть курсовая работа по автоматам, которая действительно беспокоит меня своей сложностью. Сегодня я провел почти 5 часов, не зная, правильно это или нет. Задача состоит в том, чтобы написать Java-код, который будет определять, является ли...
1172 просмотров
schedule
04.01.2023
Матрица теоремы Майхилла-Нероде для автоматов
Я успешно реализовал теорему Майхилла-Нероде на C ++. Когда завершается минимизация данного автомата, в качестве ответа выдается матрица.
Использование автоматов на этой странице: http://web.stcloudstate.edu/pkjha/CSCI502/Minimize.html , у меня...
246 просмотров
schedule
19.09.2022
Использование условия 3 леммы о накачке для доказательства неправильности
Итак, я просматривал книгу Сипсера по теории вычислений, и одно из упражнений:
Пусть B — язык {0^n1^n | n≥0}.
Докажите, что B не является регулярным.
Книга продолжает давать доказательство с использованием леммы о накачке, допуская s = 0 ^...
114 просмотров
schedule
10.05.2022
Связь между двумя конечными автоматами в Java
Я использую простой подключаемый модуль eclipse для создания визуальных машин состояний, называемых диаграммами состояний , которые также используют для работы код Java. Моя общая цель — заставить две конечные машины общаться друг с другом через...
460 просмотров
schedule
24.02.2023
Создание автомата выталкивания для обеспечения двух одинаковых вхождений подстроки
Меня попросили создать автомат выталкивания вниз (PDA), чтобы убедиться, что количество подстрок 01 равно 10 подстрокам, а также количество подстрок 00 равно 11 подстрокам.
Вот проблема:
Пусть L1 ⊆ {0, 1}* будет языком строк, которые имеют...
922 просмотров
schedule
21.07.2023
