regex - 正则表达式。定期还是不定期？

Question

我只是想对这些表达式以及它们是不规则的还是规则的有第二个看法。

{0^n 1^m | n >= m >=0} 常规的

{0^n 1^m | n,m >=0}*常规的

{0^n 0^n | n>=0}不规律的

任何人都可以确认这是真的吗？

Answer 1

{0^n 1^m | n >= m >=0}由于 FSM 无法跟踪 n 是什么以确保 n>=m，因此 FSM 无法表示表达式。

{0^n 1^m | n,m >=0}*-- FSM 似乎可以代表这一点，但存在问题。与第一个问题不同，n 和 m 彼此无关，因此没有 FSM 创建问题。问题是 n 和 m 必须在多次通过机器时保持相同。同样，由于没有记忆，这是不可能的。

{0^n 0^n | n>=0}-- 这对于 FSM 也很简单。它看起来很像第二个问题的 FSM。有(00)*