computation-theory

1зной

1ответ

Если детерминированная машина Тьюринга решает язык L, означает ли это, что он также решает L's дополнение?

Предположим, что существует детерминированная машина Тьюринга, например. который запускается в полиномиальное время и решает язык L. Это автоматически означает, что он также решает язык языка L? Когда

0зной

1ответ

Описывая действие машина Тьюринга

Я пытаюсь ответить на третью часть на следующий вопрос: я нарисовал следующую диаграмму состояний: В соответствии с решением машина «добавляет 1 к двоичному числу с наименее значимым битом в крайнем л

2зной

1ответ

Используя условие 3 насосной леммы доказать неправильность

Итак, я шел через книгу Sipser по теории вычислений, и один из упражнений: Пусть В языке {0^n1^n | n≥0}. Доказательство B не является регулярным. Книга продолжает давать доказательство, используя лемм

6зной

4ответ

Руководство по алгоритмическому мышлению (уравнение четырех четвертей)

Недавно я увидел логическую/математическую задачу 4 Fours, где вам нужно было использовать 4 четверки и ряд операторов для создания уравнений, равных целым числам от 0 до N. Как вы собираетесь писать

0зной

1ответ

Бесконтекстная грамматика для языка L = a^(2^k)

Как часть упражнения теории вычислений, меня попросят найти свободный контекст для языка L = a^(2^k). Как я попытался решить эту проблему: я хочу работать с предложением, которое рекурсивно удваивает

-4зной

1ответ

Что такое тип языка для

{xwx|x€{a,b}+,w€{a,b}+} Является ли он регулярным или CFG? Как я вижу, я могу написать его как (a+b)(a+b)+(a+b). Так что это должно быть регулярно, но я не уверен.

2зной

1ответ

убыстрены код, который вызывает те же функции снова и снова

У меня есть матрица сказать размера M X N. я должен назвать ту же функцию для каждого столбца в матрице. До сих пор я был , извлекая каждую колонку и вызывая функцию над столбцом итерации до N. т. е.

-5зной

1ответ

Язык доказательства Turing-decidable

Здравствуйте, я должен подтвердить, что: Позвольте L_1, L_2, L_3 быть Turing-узнаваемый язык, такой как L_1 U L_2 U L_3 = {a, b}* and (L_i [intersection] L_j = [empty-set]) для любых 1<=i<j<=3. Показа

2зной

2ответ

Что означает символ фантазии R, как написано здесь?

Это заданный вопрос, который у меня есть, и я не уверен, как интерпретировать R-образный символ в позиции экспоненты. Означает ли это, что машина Тьюринга должна принимать переменные числа повторений