Описание тега automata-theory
Теория автоматов изучает классы алгоритмов, которые могут быть определены с помощью абстрактных машин (автоматов). Классы автоматов различаются ограничениями, которым они подвержены; для наиболее распространенных классов основное различие касается памяти и способов доступа к ней при переходах между состояниями. Более мощные классы могут определять более мощные алгоритмы; согласно тезису Чёрча-Тьюринга, нет реальной машины более мощной, чем машины Тьюринга.
0
ответов
Возможно ли иметь производство с одним или несколькими терминалами в LHS рекурсивно перечислимого языка?
Поскольку рекурсивно перечислимая грамматика не ограничена, возможно ли иметь производство с одним или несколькими терминалами в LHS (т.е. без нетерминалов)?
18 ноя '17 в 08:56
1
ответ
Контекстная грамматика для этого языка
Я работаю над некоторыми материалами для подготовки к тестам и застрял в этой проблеме. Показать контекстную грамматику для L = {w e {a,b}*: w = wR, и за каждым a сразу следует a b}. WR это W в обратном порядке. Так, на английском языке, за палиндро…
24 фев '11 в 14:39
1
ответ
NFA для реализации DFA в C++
Название говорит само за себя. Мне нужны некоторые идеи. Вход nfa выглядит следующим образом и не имеет эпсилон-движений. 1 2 0 a 2 1 b 3 и т. д., что означает, что 1 и 2 являются конечными состояниями и что с помощью "а" я могу перейти из состояния…
23 апр '17 в 19:19
3
ответа
Регулярное выражение в DFA
Может кто-нибудь сказать мне, правильно ли подключен DFA? Я предполагаю дать DFA для языка с алфавитом Σ ={a, b} Мне нужен DFA для этого ----> A={ε, b, ab}
24 сен '15 в 01:09
1
ответ
Реализация NFA для ходов на шахматной доске 3X3
У меня есть следующая шахматная доска: Каждый квадрат - это состояние. Начальное состояние - "а". Учитывая пользовательский ввод цвета квадратов, куда он хочет переместиться, программе необходимо найти все возможные маршруты в соответствии с этим вв…
04 ноя '17 в 05:14
1
ответ
Строки, генерирующие регулярные выражения
Кто-нибудь может сказать мне, какие строки могут быть сгенерированы из регулярного выражения (a+b)*? Может ли он генерировать abbbb и ababab.? Любая помощь будет оценена.
19 дек '17 в 17:07
0
ответов
TOC: дополнение рекурсивно перечислимых языков
Существует ли какой-либо один случай, когда дополнение рекурсивно перечислимого также рекурсивно перечислимо?Или это никогда не будет рекурсивно перечислимым.
24 дек '18 в 09:09
1
ответ
Обработка естественного языка (НЛП)
С развитием технологий индустрия движется к автоматизации и интеллектуальности. В этом отношении искусственный интеллект и машинное обучение сыграли важную роль. Обработка естественного языка (NLP) - это область компьютерных наук и лингвистики, кото…
26 янв '18 в 13:13
3
ответа
Решите трехбуквенную строку в способе регулярного выражения
Мне нужна помощь, чтобы решить с помощью регулярных выражений. The language of all strings defined over Σ = {X, Y, Z} with Y as the third letter and Z being the second last letter,
21 май '15 в 12:07
1
ответ
Как определить грамматику LR(0) или SLR(1)?
Это грамматика LR(0) или SLR(1)? S -> E $ E -> T + E | T T -> x
16 июл '15 в 12:32
1
ответ
Является ли OpenGL "конечным автоматом"?
OpenGL обычно описывается как "конечный автомат", потому что, насколько я знаю, он состоит из глобальных переменных, которые могут быть установлены через его API, и они изменяют / определяют его поведение. Например, можно установить текущий цвет или…
09 апр '16 в 02:57
1
ответ
Какова связь между деривацией и деривационными деревьями?
Это было написано в книге Уллмана, но я плохо понимал, как это работает. Кто-нибудь может объяснить даже в простом контексте? Я был бы очень рад.
26 янв '17 в 10:02
1
ответ
Зачем нажимать на автоматы нужен начальный символ стека?
При определении перехода грамматики CFG или типа 2 с помощью КПК нам понадобится начальный символ стека, в основном обозначаемый Zo. я сомневаюсь, зачем нам это нужно, потому что, наконец, мы собираемся очистить стек вообще....
10 апр '15 в 18:32
1
ответ
Он-лайн симуляция двухголовочной ленты машины Тьюринга с использованием одноголовочной ленты
У меня есть вопрос, и я еще не смог найти ответ. Мне нужно провести онлайн-симуляцию двухголовочной ленты машины Тьюринга с использованием одноголовочной ленты. Я нашел несколько статей в Интернете о том, что одной ленты с одной головкой недостаточн…
13 сен '12 в 00:01
1
ответ
Может ли обычный язык иметь линейный ограниченный автомат
Как говорится в вопросе: Я пытаюсь понять автоматы. Может ли каждый регулярный язык иметь линейный ограниченный автомат?
30 мар '13 в 22:37
1
ответ
Автоматы - Построить NFA, используя копии DFA - формальное определение NFA
Я пытаюсь научиться решать следующее упражнение. Я не понимаю, как начать, это ошеломляет. Я понимаю DFA, NFA и как конвертировать DFA в NFA. Я также понимаю формальные обозначения. Это не домашнее задание, оно просто для учебы. У меня есть решение,…
28 ноя '17 в 11:53
1
ответ
Регулярное выражение в теории автоматов?
У меня есть следующий язык и его регулярное выражение {w ∈ {a, b}*: w имеет bab в качестве префикса, а babaa в качестве суффикса} Ответ: Регулярное выражение = bab(a ∪ b)*babaa, babaa, bababaa Зачем нужна жирная часть?
24 май '17 в 00:48
1
ответ
Как сгенерировать синтаксическое дерево для конкретного предложения типа a+b*c, где id->a|b|c?
Рассмотрим грамматику: E-> E+E|EE|E*E|E/E|(E)|id Я пытался по крайней мере 5 часов, чтобы решить эту проблему, но не смог. Пожалуйста, скажите мне, в чем идея решить эту проблему? Как это реализовать?
27 окт '17 в 01:57
1
ответ
Дайте контекстно-свободные грамматики, которые генерируют следующий язык
Дайте контекстно-свободные грамматики, которые генерируют следующий язык. Во всех частях алфавит ∑ равен {x,s}. {Ш | w начинается и заканчивается различными символами}
07 фев '17 в 13:11
5
ответов
Конечность обычного языка
Мы все это знаем (a + b)* это обычный язык, содержащий только символы a а также b, Но (a + b)* является строкой бесконечной длины, и она регулярна, поскольку мы можем построить конечные автоматы, поэтому она должна быть конечной. Может кто-нибудь об…
27 дек '13 в 16:13