computation-theory

-1зной

1ответ

проверки, если регулярный язык приведена CF грамматика

У меня есть эта грамматика S->aSbA S->e A->aB B->bA Как я могу определить, является ли язык регулярно? Моя проблема в том, что у A и B нет терминального символа, поэтому я не знаю, какие языки он буде

0зной

3ответ

Может ли конечный автомат существовать без какого-либо конечного состояния?

Не имеет смысла создавать акцептор языка, который не может принять какой-либо язык. Я специально говорю о FA, которые принимают языки, не являющиеся преобразователями или переводчиками, которые перево

2зной

1ответ

Количество элементов, которые удовлетворяют соотношению

Учитывая два массива: 2 5 6 4 3 7 1 5 1 6 2 3 7 4 сосчитать число элементов x, y, которые удовлетворяют условию, что x находится перед y в обоих массивах. Прогресс до сих пор: Отсортировать массивы

0зной

1ответ

теорема CAP: Могу ли я иметь последовательность и доступность в то же время

Вики говорит: один тогда остается два варианта: согласованность и доступность Почему я не могу избавиться от толерантности Partition? Что означает допустимость раздела?

1зной

1ответ

Упрощение лямбда-производств, унарные правила и неопасные символы грамматики

Я знаю, что это не общий вопрос, но я хотел бы знать, как это сделать, например, я уже немного работал над это ... После этого: У меня есть следующая грамматика. Я попытался упростить его, но я не уве

1зной

1ответ

Алгоритм: Вставка в список пропусков

Как выглядит алгоритм вставки в список пропусков? Обычно что-то вроде this появляется при поиске в google, но, как ни странно, я не могу найти ничего полезного в своей книге или в Интернете. Единствен

0зной

1ответ

Возможно ли сокращение от P до NP?

Если X является поли-временем, приводимым к Y, мы ничего не можем сказать о X, даже если Y является NP-жестким, поэтому должны существовать некоторые разрешимые проблемы polytime, которые могут быть с

1зной

1ответ

Для обычного языка a * b * существует ли его надмножество, которое является нерегулярным?

Язык A = a*b* - это абсолютно обычный язык. Но мне интересно, есть ли надмножество его нерегулярного языка? И надмножество должно использовать один и тот же алфавит {a, b}