grammar - 除了语法之外，还有其他方法可以描述形式语言吗？

Question

我正在寻找处理一般描述形式语言（字符串集）而不仅仅是语法层次结构的数学理论。

Answer 1

例如，正则表达式是描述一组语言的一种形式。尽管有两种方式转换正则语法和表达式的算法，但它们仍然是两种不同的理论。此外，自动机（作为自动机的复数形式）可以帮助您描述语言，不仅仅是描述与常规语言相同的集合的 DFA 和 NFA，而是 2DFA，堆栈自动机。例如，两栈自动机与图灵机一样强大。最后，图灵机本身就是语言的一种形式。对于任何图灵机，给定图灵机在有限步数上停止的所有字符串的集合是正式定义的语言。

Answer 2

语法为您提供了列出语言中所有可能字符串的算法。您可以以任何其他方式指定算法，但语法是一种简洁且广为接受的格式。

另一种方法是列出属于该语言的每个字符串——这只有在语言中的字符串集很小的情况下才有效（当集合是无限的时候肯定不行）。