grammar - 文法以外の形式言語を記述する他の方法はありますか？

Question

文法階層だけでなく、一般的な形式言語（文字列のセット）の記述を扱う数学的理論を探しています。

Answer 1

正規表現は、たとえば一連の言語を記述するための形式です。正規の文法と正規表現を両方の方法で変換するアルゴリズムはありますが、それらはまだ 2 つの異なる理論です。また、オートマトン (オートマトンの複数形) は、通常の言語と同じセットを記述する DFA や NFA だけでなく、スタック オートマトンである 2DFA などの言語を記述するのにも役立ちます。たとえば、2 スタック オートマトンはチューリング マシンと同じくらい強力です。最後に、チューリング マシン自体は言語の形式主義です。任意のチューリング マシンの場合、特定のチューリング マシンが有限数のステップで停止するすべての文字列のセットは、正式に定義された言語です。

Answer 2

文法は、言語で可能なすべての文字列をリストするアルゴリズムを提供します。他の方法でアルゴリズムを指定することもできますが、文法は簡潔で広く受け入れられている形式です。

もう 1 つの方法は、その言語に属するすべての文字列を一覧表示することです。これは、言語の文字列のセットが小さい場合にのみ機能します (セットが無限の場合は確実に機能しません)。