Вопросы по теме 'automata-theory'
Каков типичный размер алфавита конечных автоматов?
Не совсем уверен, что это правильный форум, но в Theoretical Computer Science было предложено перенести его сюда...
Каков типичный размер алфавита конечных автоматов?
В настоящее время я занят реализацией высокопроизводительной библиотеки FA, и...
545 просмотров
schedule
01.06.2023
LR(1) - Предметы, смотреть вперед
У меня возникли трудности с пониманием принципа просмотра в LR(1) - items. Как вычислить упреждающие наборы?
Скажем, например, что у меня есть следующая грамматика:
S -> AB
A -> aAb | b
B -> d
Тогда первое состояние будет...
6668 просмотров
schedule
16.06.2023
Можно ли объединить конечные и неконечные состояния, имеющие одинаковые конфигурации, в минимальном DFA?
Я практиковал некоторые вопросы по теории автоматов, где я столкнулся с вопросом о минимальном dfa, в котором я не могу понять, где я ошибся. Я получаю 4 состояния в минимальном dfa, но моя книга говорит, что ответ равен 3. вопрос просит данный NFA...
404 просмотров
schedule
18.06.2023
DFA для этого языка
Σ={ a, b, c, d } L={ x ∈ Σ* | x не начинается и не заканчивается на "bab" }
Примеры, которые следует принять:
абаба
аббревиатура
ббабб
ббаба
ab
ba
аааа
ɛ
Примеры, от которых следует отказаться:
баб
баба
бабк...
232 просмотров
schedule
24.06.2023
Реализация недетерминированного конечного автомата (NFA)
Я пытаюсь разработать симуляцию, которая выполняет недетерминированный конечный автомат на Java. Первый аргумент командной строки — это текстовый файл, определяющий машину. Второй аргумент — это входная строка. Если он принимает строку, он печатает...
4987 просмотров
schedule
17.08.2022
Некоторые NFA, ОБЫЧНЫЙ ЯЗЫК и эквиваленты
Я прочитал какую-то заметку о Automaton Course. я вижу это примечание, что после все то же самое. но я думаю, что L(g) не равно NFA и регулярному выражению. кто-нибудь может помочь мне с определением языка этих фигур (nfa, регулярное выражение и...
137 просмотров
schedule
14.01.2024
Могу ли я использовать стек в машине Тьюринга?
Я пытаюсь разработать машину Тьюринга, которая принимает язык L = {w | a n b 2n }, где ∑ = {a, b}.
Например, машина принимает ввод: «aabbbb», но не принимает «aabb».
Мой код ниже об этом языке;
#include <iostream>
#include...
1066 просмотров
schedule
02.11.2022
Эквивалентности линейной временной логики
для формулы LTL FG p & FG q я хочу отвергнуть или отвергнуть, что она эквивалентна F (G p & Gq) . Я думаю, что по закону распределения мы можем записать F(Gp&Gq) как FG(p&q) . мы также можем сказать FG p & FG q =...
68 просмотров
schedule
21.02.2023
Что означает длина паландромы в теории автоматов? даже палиндром? странный палиндром?
Палиндром — это язык в автоматах. Но я не могу понять следующий абзац. Я многое рассчитал и изо всех сил пытался оценить, но не смог.
Длина палиндрома: Поскольку мы знаем, что строка имеет длину n, а количество символов в алфавите равно 2, это...
400 просмотров
schedule
16.06.2023
Как факторизовать строку, чтобы проверить ее принадлежность к языку, сгенерированному из алфавита?
Пусть S = {a, bb, bab, abaab} — алфавит. а замыкание клини будет S* для всех возможных комбинаций.
Существует ли строка abaabbabbabaab в S*?
каков метод факторизации, чтобы проверить, находится ли он в S * или нет? Я сделал это следующими...
74 просмотров
schedule
21.12.2022
Регулярное выражение над языком C={a,b}
Добрый вечер всем, я застрял со следующим регулярным выражением,
Я думаю, что есть гораздо более простой подход к выражению, чем мой,
Мне пришлось записать регулярное выражение и dfa, которые из алфавита {a,b} принимали все строки, начинающиеся...
89 просмотров
schedule
30.01.2023
Могу ли я классифицировать грамматику на основе сравнения длины
Всякий раз, когда у нас есть обычный язык, у нас не может быть сравнения (по очевидной причине, что у него нет памяти). А когда у нас контекстно-свободный язык, у нас может быть сравнение Max 1. Например, a ^ n b ^ n здесь длина a и b имеет только...
56 просмотров
schedule
14.05.2024
Строить решающую машину, а не решающую машину Тьюринга
Как сделать граф машины Тьюринга, который распознает all words with an even number of a's , но является not a decider и ничем другим. Кроме того, как сделать decider машинный граф Тьюринга для того же языка.
61 просмотров
schedule
30.12.2023
Построение графа машины Тьюринга
Я пытался сделать граф машины Тьюринга, распознающий язык:
{(ab)^n(ba)^n | n >0}
Как построить граф машины Тьюринга для вышеупомянутого языка?
32 просмотров
schedule
09.12.2022
Как создаются компьютерные языки с использованием концепции теории автоматов?
Я очень старался найти ответ на этот вопрос в движке Google.
Но мне интересно, как эти языки программирования высокого уровня созданы по принципу автоматов, или теория автоматов не включена в определение языков?
109 просмотров
schedule
23.01.2023
Является ли данный язык допустимым CFG?
Язык, L = {a^n b^n a^n; п=1,2,3,.. }
Я хочу проверить, является ли данный язык L контекстно-свободным или нет.
CFG использует PDA, который использует стеки. Итак, сначала сохраните каждую букву «а» в стеке. Затем нажмите дважды для каждого...
56 просмотров
schedule
06.10.2023
Как мне построить этот автомат выталкивания, следуя этим правилам
Правила таковы: он не может начинаться с буквы а. Он не может заканчиваться на букву б. Он должен содержать b=i a=2i. Алфавит а, б. Я пытался очистить стек. Но, к сожалению, я не могу добраться до него. Например, такой ввод: bbaaaa это...
58 просмотров
schedule
17.09.2022
