正規言語表現を構築する一般的な複雑さは何ですか？

Question

言語の正規表現を持っていると便利なことがよくあります（私の場合、通常はドメイン固有の言語です）。ただし、その言語の任意のプログラムに対して標準形式を決定および/または作成できるかどうかを決定する、関連する言語の表現力には厳しい制限があると思います。残念ながら、これについて読んだことを（漠然と）思い出した参考文献を見つけることができませんでした。

一方で、言語の標準的な表現を作成することは、多くの困難なグラフ問題（例：グラフ同型）に匹敵する複雑さですが、一方で、iirc、gcc、yhc、ghcのようなコンパイラ中間表現を使用して、さまざまな形式（アセンブリ、javascriptなど）で出力を生成します。これにより、少なくとも一部の形式では解決された問題になります。

特定の言語の標準形式を決定/生成できるのはいつですか？ （その言語はどの程度表現力があり、言語表現力は標準形式の有用性にどのように影響しますか？）可能な場合は、参照または証明を提供してください。

編集：たとえば、通常言語（例： ：正規表現の「純粋な」形式）は、チューリング完全言語と同じものの多くを表現できませんできます。言い換えれば、通常の言語でWebサーバーを作成することはできませんが、ラムダ計算を使用することはできます。私の質問は理論的な可能性に関するものであり、複雑性理論に関する具体的な答えがあります。別のシステムに送信する必要のあるDSLがある場合、送信する前にそのコードの標準形式を生成することは、2つの異なるシステムで使用される独立した表現を分離するため、しばしば有益です。 ただし、P-Space complete、またはチューリング完全言語を標準形式に翻訳するNP-Completeであれば、標準形式を構築しようとして時間を無駄にしないでください。別の方法、または言語の複雑さを多項式時間で正規化できるものに 減らすことができます。

Answer 1

「正規表現」による;私はあなたが次のことを意味すると仮定します：プログラムが「同じことをする」 P と Q 同等を呼び出す同じ入力で。 「同じことをする」は、プログラムの出力が同じであり、両方のプログラムが有限時間後に停止するか、両方とも無限ループに入ることを意味します。この等価関係は、すべてのプログラムのセットで等価クラスを定義します。 「正規表現」プログラムの P は同じ等価クラスに属するプログラム P 'であり、同じ等価クラスのすべてのメンバーが同じ標準表現を持っている必要があります。

チューリング完全言語の場合、チューリングで計算可能な正規表現を使用すると、 Haltingの問題を解決できます次のように：最初に無限ループで構成されるプログラムを記述し、その正規表現 Q を見つけます。次に、入力プログラム P について、最初に出力を生成しないことを除いて同じことを行うプログラム P ₀ に機械的に変換します。次に、このプログラムの正規表現 P ₀ 'を見つけます。結果が Q の場合、 P ₀ は停止せず、したがって P も停止しません。それ以外の場合、 P ₀ は停止し、 P も停止します。

さらに楽しくするために、グレゴリー・チェイチンの作品を読んでください。エレガント＆quot;プログラム。

Answer 2

アセンブリ言語へのコンパイルは、実用的な方法で標準形式への翻訳として分類できるように思えます。