Редактирование: Список заданий по ДМ 2020 весна
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 166: | Строка 166: | ||
# Грамматика называется леворекурсивной, если найдется такой нетерминал A, что за один или более шаг из A можно вывести строку, которая начинается с A ($A \Rightarrow^+ A\alpha$). Предложите алгоритм, который проверяет, является ли грамматика леворекурсивной. | # Грамматика называется леворекурсивной, если найдется такой нетерминал A, что за один или более шаг из A можно вывести строку, которая начинается с A ($A \Rightarrow^+ A\alpha$). Предложите алгоритм, который проверяет, является ли грамматика леворекурсивной. | ||
# Предложите алгоритм проверки, что в заданная КС грамматика в НФХ порождает конечное число слов. | # Предложите алгоритм проверки, что в заданная КС грамматика в НФХ порождает конечное число слов. | ||
− | # Предложите алгоритм, который получает на вход КС грамматику в НФХ, про которую с помощью алгоритма из предыдущего задания выяснили, что она порождает конечное число слов. На выход необходимо выдать самое длинное слово, которое порождается этой КСГ. | + | # Предложите алгоритм, который, получает на вход КС грамматику в НФХ, про которую с помощью алгоритма из предыдущего задания выяснили, что она порождает конечное число слов. На выход необходимо выдать самое длинное слово, которое порождается этой КСГ. |
# Билл поменял местами шаги алгоритма приведения КСГ к НФХ: он сначала удаляет цепные правила, а затем eps-правила. Будет ли корректно работать алгоритм? | # Билл поменял местами шаги алгоритма приведения КСГ к НФХ: он сначала удаляет цепные правила, а затем eps-правила. Будет ли корректно работать алгоритм? | ||
# Билл поменял местами шаги алгоритма приведения КСГ к НФХ: он сначала удаляет eps-правила, а затем длинные правые части. Можно ли поправить алгоритм удаления eps-правил, чтобы он работал с длинными правыми частями? Чем эта версия алгоритма хуже оригинальной? | # Билл поменял местами шаги алгоритма приведения КСГ к НФХ: он сначала удаляет eps-правила, а затем длинные правые части. Можно ли поправить алгоритм удаления eps-правил, чтобы он работал с длинными правыми частями? Чем эта версия алгоритма хуже оригинальной? |