Как вызвать структурированный язык, который не может зацикливаться или функциональный язык, который не может вернуть

Question

Я создал специальное «язык программирования», который намеренно (по дизайну) не может дважды оценивать один и тот же кусок кода дважды (т.е. он не может цикл). По сути, он сделан для описания процесса, похожей на блок-схему, в котором каждый элемент в блок-схеме является условным, который выполняет другой тест на одном и том же наборе данных (без возможности его модифицировать). Ветви могут разделить и слияние, но никогда не в круговом манере, т.е. Блок -схема не может вернуться назад на себя. При прибытии в конце филиала текущее состояние возвращается, а программа выходит.

При записи, типичная программа поверхностно напоминает программу на чисто функциональном языке, за исключением того, что форма рекурсии не разрешена, и функции никогда не могут ничего вернуть; Единственный способ выйти из функции - это вызвать другую функцию или вызвать общий оператор по выходу, который возвращает текущее состояние. Аналогичный эффект также может быть достигнут путем принятия структурированного языка программирования и удаления всех операторов цикла или за счет «неструктурированного» языка программирования и запрещения любого заявления GOTO или JMP, который идет задом наперед в коде.

Теперь мой вопрос: есть ли краткий и точный способ описать такой язык? У меня нет официального фона CS, и мне трудно понять статьи об теории автоматов и формальной теории языка, поэтому я немного не могу. Я знаю, что мой язык не завершен, и благодаря большой боли мне удалось заверить себя, что мой язык вероятно Можно ли классифицировать как «обычный язык» (т.е. язык, который можно оценить с помощью машины Тьюринга только для чтения), но есть ли более конкретный термин?

Бонусные баллы, если термин интуитивно понятен для аудитории, которая хорошо разбирается в общих концепциях программирования, но не имеет формального фона CS. Также бонусные баллы, если есть определенный вид машины или автомата, который оценивает такой язык. О да, имейте в виду, что мы не оцениваем поток данных - каждый элемент имеет (только для чтения) доступ к полному набору входных данных. :)

Answer 1

Я знаю, что этот вопрос несколько старый, но для потомства, фраза, которую вы ищете, - это «дерево решений». Видеть http://en.wikipedia.org/wiki/decision_tree_model Для деталей. Я считаю, что это фиксирует именно то, что вы сделали, и у него есть довольно описательное имя для загрузки!

Answer 2

Я считаю, что ваш язык достаточно мощный, чтобы кодировать именно Языки без звезд. Анкет Это подмножество этих обычных языков, на которых ни одно выражение не содержит звезды Kleene. Другими словами, это язык пустой строки, нулевой набор и отдельных символов, которые закрыты при объединении и дизъюнкции. Это эквивалентно набору языков, принятых DFA, у которых нет направленных циклов.

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

1. Никакие функции никогда не возвращаются. После того, как функция будет вызвана, она никогда не вернет поток управления в абонент.
2. Все вызовы разрешаются статически (то есть вы можете посмотреть на исходный код и построить график каждой функции и набор функций, которые он вызывает). Другими словами, нет никаких указателей функций.
3. График вызовов ациклический; Для любых функций A и B, то именно одно из следующих действий: транзитивно вызывает B, B транзитивно вызывает, или ни A, ни B транзисивно вызывают друг друга.
4. В целом, график потока управления является ациклическим. Как только выражение оценивается, оно никогда больше не оценивается. Это позволяет нам обобщать вышеупомянутое, чтобы вместо того, чтобы думать о функциях, вызывающих другие функции, мы можем думать о программе как о серии утверждений, которые все называют друг друга как DAG.
5. Ваш вход - это строка, в которой каждая буква сканируется один раз и только один раз, и в порядке, в котором она дана (что кажется разумным, учитывая тот факт, что вы пытаетесь моделировать блок -схемы).

Учитывая эти предположения, вот доказательство того, что ваши программы принимают язык, если этот язык не является звездой.

Чтобы доказать, что если есть язык без звезды, на вашем языке есть программа, которая принимает его, начните с построения DFA минимального состояния для этого языка. Языки без звезд не содержат петли и сканируют ввод ровно один раз, и поэтому должно быть легко создать программу на вашем языке с DFA. В частности, учитывая государство s С набором переходов в другие состояния, основанные на следующем символе ввода, вы можете написать функцию, которая рассматривает следующий символ ввода, а затем вызывает функцию, кодирующую состояние, переходящее. Поскольку DFA не имеет направленных циклов, вызовы функций не имеют направленных циклов, и поэтому каждый оператор будет выполнен ровно один раз. Теперь у нас есть это (∀ R.-это язык без звезды → ∃ Программа на вашем языке, которая принимает его).

Чтобы доказать обратное направление значения, мы по существу обратили вспять эту конструкцию и создаем ε-NFA без циклов, которые соответствуют вашей программе. Выполнение подмножества на этом NFA, чтобы уменьшить его до DFA, не будет ввести циклы, и поэтому у вас будет язык без звезды. Строительство следующая: для каждого заявления s_я В вашей программе создайте состояние Q_я с переходом к каждому из состояний, соответствующих другим заявлениям в вашей программе, которые находятся в стороне от этого утверждения. Переходы к этим состояниям будут помечены символами, потребляемыми входом, принимающим каждое из решений, или ε, если переход происходит без использования каких -либо входов. Это показывает, что (∀ Программы P на вашем языке и существует; беззвездочный язык R принимает только строки, принятые вашим языком).

Взятые вместе, это показывает, что ваши программы имеют идентичную силу языков без звезд.

Конечно, предположения, которые я сделал о том, что могут сделать ваши программы, могут быть слишком ограничены. У вас может быть случайный доступ к входной последовательности, которую я считать можно обработать с модификацией вышеуказанной конструкции. Если у вас могут быть циклы исполнения, то вся эта конструкция разрывается. Но даже если я ошибаюсь, мне все еще было очень весело думать об этом, и спасибо за приятный вечер. :-)

Надеюсь это поможет!