computation-theory

0зной

1ответ

Бесконечный союз обычного языка может быть свободным от контекста. Является ли это утверждение истинным или ложным? В соответствии с ответом, это правда! Я знаю, что бесконечное объединение или пересе

0зной

2ответ

Можно ли вычислить функцию подсчета и произведение последовательных простых чисел в полиномиальное время?

В двух алгоритмов я работал с, я использую две функции: пи (п): = число простых чисел < = п и Р (п): = г, где прода (p_i, г = 1, г) < = п но п < прод (p_i, г = 1, г + 1), гдеp_i является I-е простым.

0зной

2ответ

Context Free способен генерировать все обычные языки?

Я в настоящее время изучаю теорию вычислений, где я наткнулся на заявлении, « CFG также может создать регулярный язык» или она должна быть все CFG могут создавать все (любые) регулярные язык

0зной

2ответ

Хомский алгоритм преобразования нормальной формы

Почему мы добавляем новое начальное состояние S0 -> S, когда хотим преобразовать грамматику в нормальную форму Хомского? Что не так, если мы этого не сделаем? Сначала я думал, что это из-за правил eps

0зной

1ответ

R: На какой глубине должен иметь место параллельный вызов

У меня есть вложенные *apply звонки, и я хочу распараллелить их. У меня есть возможность распараллеливать либо верхний вызов, либо вложенный внутренний вызов. Я считаю, что теоретически первый из них

0зной

1ответ

Язык, который является RE полным в отношении сокращений полиномиальных времен?

Есть ли какой-либо язык в RE, который является полным в отношении сокращений полиномиального времени? Я думаю, что A_TM будет хороший пример, но я не уверен ...