regex - 正規表現。定期的または不定期？

Question

私はこれらの表現について、そしてそれらが不規則であるか規則的であるかについて、2番目の意見を得たいと思います。

{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> = mを保証するために、nが何であったかを追跡できないため、FSMは式を表すことができません。

{0^n 1^m | n,m >=0}*--FSMはこれを表しているように見えますが、問題があります。最初の問題とは異なり、nとmは互いに無関係であるため、FSM作成の問題はありません。問題は、マシンを複数回通過する場合、nとmが同じままでなければならないことです。繰り返しますが、メモリがないため、これは不可能です。

{0^n 0^n | n>=0}--これはFSMでも簡単です。2番目の問題のFSMによく似ています。がある(00)*