ループできない構造化された言語や、戻ることができない機能的言語を呼び出す方法

Question

意図的に（設計上）同じコードを2回評価できない特別な目的の「プログラミング言語」を作成しました（つまり、ループできません）。基本的に、フローチャートの各要素が同じデータセットで異なるテストを実行する条件付き（変更できない）条件付きであるフローチャートのようなプロセスを説明するように作られています。枝は分割してマージすることができますが、決して円形ではありません。フローチャートはそれ自体に戻ることができません。支店の終わりに到着すると、現在の状態が返され、プログラムが終了します。

書き留めた場合、典型的なプログラムは表面的に純粋に機能的な言語のプログラムに似ていますが、再帰の形式は許可されておらず、関数は何も返さないことを除いて。関数を終了する唯一の方法は、別の関数を呼び出すか、現在の状態を返す一般的な出口ステートメントを呼び出すことです。また、構造化されたプログラミング言語を取得し、すべてのループステートメントを削除するか、「構造化されていない」プログラミング言語を取得し、コードを逆にするGOTOまたはJMPステートメントを禁止することにより、同様の効果を達成できます。

さて、私の質問は次のとおりです。そのような言語を説明する簡潔で正確な方法はありますか？私は正式なCSの背景を持っていないので、オートマトン理論と正式な言語理論に関する記事を理解することは難しいので、私は少し途方に暮れています。私は自分の言語が完全にチューリングしていないことを知っています、そして、私は自分の言語を自分自身に保証することができました おそらく 「通常の言語」（つまり、読み取り専用のチューリングマシンで評価できる言語）として分類できますが、より具体的な用語はありますか？

ボーナスポイントという用語が、一般的なプログラミングの概念に精通しているが、正式なCSの背景を持っていない視聴者にとって直感的に理解できる場合。また、そのような言語を評価する特定の種類のマシンまたはオートマトンがある場合、ボーナスポイント。そうそう、データのストリームを評価していないことに留意してください。すべての要素には、入力データの完全なセットへの（読み取り専用）アクセスがあります。 :)

Answer 1

私はこの質問がやや古いことを知っていますが、後世のために、あなたが探しているフレーズは「決定ツリー」です。見る http://en.wikipedia.org/wiki/decision_tree_model 詳細については。これはあなたがやったことを正確に捉えており、起動するのにかなり説明的な名前を持っていると思います！

Answer 2

私はあなたの言語が正確にエンコードするのに十分なほど強力であると信じています 星なしの言語. 。これは、クリーンの星を含む表現がない通常の言語のサブセットです。言い換えれば、それは空の文字列、ヌルセット、および連結と分離の下で閉じられている個々の文字の言語です。これは、指示されたサイクルが含まれていないDFAによって受け入れられている言語のセットに相当します。

あなたの言語の説明を考えると、ここでこれの証拠を試みることができますが、あなたの言語に完全にアクセスできないので、正確に正確に機能するかどうかはわかりません。私が行っている仮定は次のとおりです。

1. 関数は戻りません。関数が呼び出されると、コントロールにコントロールフローを返すことはありません。
2. すべての呼び出しは静的に解決されます（つまり、ソースコードを見て、各関数のグラフと呼び出す関数のセットを作成できます）。言い換えれば、機能ポインターはありません。
3. コールグラフは非環式です。任意の関数AとBの場合、次の1つが正確に保持されます。AはB bを呼び出し、bはAを通過するか、AまたはBのどちらも互いに呼びません。
4. より一般的には、制御フローグラフは非環式です。式が評価されると、二度と評価されません。これにより、上記を一般化できるようにするため、他の機能を呼び出す関数を考える代わりに、プログラムをすべてお互いをDAGと呼ぶ一連のステートメントと考えることができます。
5. 入力は、各文字が一度だけ一度だけスキャンされる文字列であり、それが与えられた順序で（フローチャートをモデル化しようとしているという事実を考えると合理的に思えます）。

これらの仮定を考えると、ここにプログラムが言語が星なしである場合、あなたのプログラムが言語を受け入れるという証拠があります。

スターフリーの言語がある場合、それを受け入れる言語にプログラムがあることを証明するには、その言語の最小ステートDFAを構築することから始めます。スターフリーの言語はループフリーで、入力を1回だけスキャンするため、DFAから言語でプログラムを簡単に作成できるはずです。特に、状態を与えられた s 次の入力記号に基づいて他の状態への一連の遷移を使用すると、入力の次の文字を調べてから、遷移する状態をコードする関数を呼び出すことができます。 DFAには指示サイクルがないため、関数呼び出しには指示サイクルがないため、各ステートメントは正確に1回実行されます。私たちは今それを持っています（∀R.はそれを受け入れる言語のプログラムです）。

含意の逆方向を証明するために、本質的にこの構造を逆転させ、プログラムに対応するサイクルなしでεNFAを作成します。このNFAをDFAに減らすためにサブセット構造を行うと、サイクルが導入されないため、星なしの言語があります。構造は次のとおりです：各ステートメントについて_私 プログラムでは、状態qを作成します_私 プログラムの他の声明に対応する各州への移行により、その声明から1つ離れています。これらの状態への遷移は、入力を消費した入力の記号でラベル付けされます。各決定を行うと、遷移が発生した場合はεが発生した場合にεにラベル付けされます。これは、（あなたの言語にpをプログラムし、存在する;星のない言語があなたの言語で受け入れられた文字列だけを受け入れることを示しています）。

まとめると、これはあなたのプログラムが同じように星のない言語の力を持っていることを示しています。

もちろん、私があなたのプログラムができることについて私が行った仮定は、あまりにも制限されているかもしれません。入力シーケンスにランダムアクセスがあるかもしれませんが、 考える 上記の構造の変更で処理できます。実行中のサイクルが可能な場合は、この構造全体が壊れます。しかし、たとえ私が間違っていたとしても、私はまだこれについて考えるのがとても楽しかったです、そして楽しい夜をありがとう。 :-)

お役に立てれば！