計算可能性理論
つまり、 ( n + d + 1 ) {\displaystyle (n+d+1)} 個の 'a' を読み込んだときと ( n + 1 ) {\displaystyle (n+1)} 個の 'a' を読み込んだときの状態が区別されない。従って、 M {\displaystyle M} が x {\displaystyle x} を受容するなら、その機械は ( n + d + 1 ) {\displaystyle (n+d+1)} 個の 'a' と ( n + 1 ) {\displaystyle (n+1)} 個の 'b' からなる文字列も受容してしまう。しかしその文字列は 'a' と 'b' が同数でないため、言語の定義からは受容してはいけない文字列なのである。
従って、この言語は有限状態機械では正しく受容できず、正規言語ではないということになる。これを一般化したものを正規言語の反復補題と呼び、各種言語クラスが有限状態機械で認識できないことを示すのに使われる。
この言語を認識できるプログラムは簡単に書けると思われるかもしれない。そして、現在のコンピュータは有限状態機械でモデル化できると上に書いてある。もちろんプログラムは書けるが、この問題の本質はメモリ容量の限界の見極めにある。非常に長い文字列を与えられた場合、コンピュータのメモリ容量が足りなくなって入力文字数を数えられなくなり、オーバーフローするだろう。その意味で、現代のコンピュータは有限状態機械と同じと言える。したがって、この言語の文字列の大部分は認識できるとしても、必ず認識できない文字列が存在する。