regular-language - ワンダーは次の言語有限です

Question

私のクラスでは、次の言語が有限であるかどうかについて質問があります

{w : w は {a ^m b ⁿ :m+n≤k}} の正規表現で、k は特定の自然数です。

言語には多くても単語が存在する可能性があるため、有限だと思います(K+1)*k/2が、参照の答えは w は無限です

誰でも説明できますか

ps: 特定の正規言語に対して正規表現は 1 つしかありませんか?

Answer 1

あなたの質問を正しく解釈すれば、ええ、それは無限大です。一致する異なる正規表現の数を探しています。たとえば、3 つの文字列 'a' と 'b' で、すべての 'a' が最初に来ます。異なる正規表現言語は、許可される構文が異なる場合がありますが、それらすべてに何らかの和集合演算子があります。パターンの 'a' を ('a' | 'a') に変更すると、もちろん 'a' になりますが、これは新しい書き方です。同じように拡張し続けることで、そのパターンを記述する方法は無数にあります。