Описание тега computation-theory
The theory of computation is the branch that deals with whether and how efficiently problems can be solved on a model of computation, using an algorithm. The field is divided into three major branches: automata theory, computability theory and computational complexity theory. [wikipedia]
1
ответ
Минимальное количество состояний необходимо?
Определение языка L с алфавитом { a } дается следующим образом L = {ank | k> 0; и n является положительной целочисленной константой} Какое количество состояний требуется в DFA для распознавания L? На мой взгляд, это должно быть k+1, но я не уверен.
13 фев '11 в 14:55
2
ответа
Вычисление O(n) для hasmap против двоичного поиска
Я пытаюсь уточнить, как рассчитать O (n) для следующего случая: Учитывая отсортированный массив, как бы вы нашли два числа, сумма которых равна заданному числу x в O (n)? Решение O (n) будет: Удалить первый элемент массива (e0) Добавьте это к хэш-ка…
20 фев '17 в 12:57
2
ответа
Накачка леммы в контекстно-свободных языках
A = {0^a 1^b 2^c | a < b < c} Мне нужно показать, что A не является контекстно-свободным. Я предполагаю, что для этого мне нужно использовать Лемму прокачки, но как?
04 ноя '10 в 10:01
1
ответ
Разрешимость трех государственных FA
Я пытаюсь выяснить, как описать пятьдесят шесть строк, чтобы проверить, имеет ли FA из трех состояний над алфавитом {a b} конечный язык. Число пятьдесят шесть происходит из теоремы, которая гласит, что если машина имеет N состояний, а алфавит состои…
08 окт '12 в 18:59
2
ответа
Нужно регулярное выражение для конечных автоматов: четное число 1 и четное число 0
Моя проблема может звучать иначе для вас. Я начинающий, и я изучаю конечные автоматы. Я пытаюсь найти в Интернете регулярное выражение для конечных автоматов данной машины. Может кто-нибудь помочь мне написать "Регулярное выражение для конечных авто…
02 июл '13 в 07:56
2
ответа
Отрицание регулярного выражения
Я не уверен, как это называется: отрицание, дополнение или инверсия. Концепция заключается в следующем. Например, имея алфавит "AB" R = 'a' !R = the regexp that matche everyhting exept what R matches В этом простом примере это должно быть !R = 'b*|[…
10 сен '12 в 10:22
1
ответ
Упрощение лямбда-производств, унарных правил и бесполезных символов грамматики
Я знаю, что это не общий вопрос, но я хотел бы знать, как это сделать, используя пример, над которым я уже немного работал.. Однажды сказал это: У меня есть следующая грамматика. Я пытался упростить его, но я не уверен в его правильности. Может ли к…
16 окт '16 в 14:43
2
ответа
Примитивная рекурсия если потом
У меня проблема с проекциями в моем определении "Если потом, остальное". Это на самом деле выполняется как If-Else-Then. import Prelude hiding (pred,and,or,not) data PR = Z | S | P Int | C PR [PR] | PR PR PR deriving Show eval :: PR -> [Integer] …
26 ноя '12 в 04:58
1
ответ
Решение TSP в лабиринте с использованием ACO
Я пишу алгоритм, который включает задачу коммивояжера и задачу решения лабиринта. По сути, в лабиринте есть точки, и нам нужно найти наиболее оптимальный путь ко всем этим точкам и в конечном итоге выйти из лабиринта. Мы начали использовать алгоритм…
23 окт '14 в 10:08
1
ответ
Устранение немедленной левой рекурсии
Я понимаю, что для того, чтобы исключить немедленную левую рекурсию из грамматики, содержащей произведение формы A⇒Aα, мне нужно заменить ее на A⇒βA'and A'⇒αA / ∈ У меня есть следующие производства, мне нужно устранить немедленную левую рекурсию E⇒E…
21 янв '14 в 09:08
3
ответа
Как я могу доказать, что этот язык является регулярным?
Я пытаюсь доказать, если этот язык: L = {w = {0,1} * | #0(w)% 3 = 0} (число 0 делится на 3) регулярно пользуется леммой прокачки, но я не могу найти способ сделать это. Все остальные примеры, которые я получил, имеют простую форму или, скажем, более…
17 дек '15 в 18:08
1
ответ
Как получить пересечение DFA?
Как объединить два dfa, используя метод пересечения?
22 июн '10 в 19:30
2
ответа
Устранение левой рекурсии
У меня есть эта грамматика S->S+S|SS|(S)|S*|a Я хочу знать, как исключить левую рекурсию из этой грамматики, потому что S+S действительно сбивает с толку...
25 дек '12 в 19:01
1
ответ
Алгоритм для распределения множества чисел в двумерном массиве без соседних самих себя
Я хочу, чтобы алгоритм распределял набор чисел, таких как (0,1...15), в большой двумерный массив с известными размерами, не позволяя числу, соседствующему себя в качестве примера: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 4 5 6 7 3 4 5 6 7 8 9 1…
15 сен '18 в 23:02
0
ответов
Полностью универсальный код на GPU
Ко мне обратился клиент для работы над проектом, который будет включать в себя попытку запуска полнофункциональных программ на GPU с OpenCL. У меня есть приличные знания CUDA и машинная архитектура низкого уровня. Насколько я понимаю, код GPU не име…
26 мар '13 в 13:00
0
ответов
КПК (Pushdown Automata) Трассировка - я не понимаю ответ
Я изучаю КПК и узнаю, как отследить набор символов или алфавит для данного нарисованного КПК. Тем не менее, я не знаю, как отследить для данного КПК (в письменной форме) см. Ниже. Итак, это письменный КПК: Q={s0,f} Σ={a,b,c} Γ={S,X,a,b,c} F={f} δ={(…
14 янв '16 в 22:05
1
ответ
Определение не зависящего от контекста грамматики для конкретного языка
У меня есть язык, в котором каждая строка в этом языке имеет четное количество 0 как 1 (например, 0101, 1010, 1100, 0011, 10 все на языке). Я надеялся определить грамматику без контекста, которая описывает этот язык. После определения грамматики без…
17 мар '14 в 21:12
1
ответ
Может ли язык принимать бесконечные числа
У меня есть вопрос, может ли язык принимать бесконечные числа Я должен уменьшить Лемпти до Линфа where Lempty ={e|L(Pe) is null} Linf={e|L(Pe) is infinite} так я могу определить программу P, как это " input n Run Pe on 1...n for n steps if Pe accept…
11 мар '13 в 00:33
1
ответ
Самая низкая вычислительная сложность (Big-O)
Из этих алгоритмов я знаю, что Alg1 - самый быстрый, так как он равен n в квадрате. Следующим будет Alg4, поскольку он имеет n куб, а затем Alg2, вероятно, самый медленный, поскольку он равен 2^n (который, как предполагается, имеет очень низкую про…
05 май '13 в 20:22
0
ответов
Пошаговое выполнение функции для моделирования машины Тьюринга?
Просто случайный вопрос - есть ли способ запустить функцию Python шаг за шагом? Я хочу иметь возможность имитировать такие вещи, как ласточкин хвост - где для каждого ввода я могу запустить один шаг функции за раз, чтобы он выводил все операторы воз…
03 май '17 в 18:34