毎年，Cのプログラミングの講義の第7回目くらいに，それまでに学んだ文法知識(データ型，制御文，演算子，配列，ポインタ)をフル活用したプログラムを紹介しています．
今年は，与えられた文字列が反復語であるかを判定するプログラムを自作し，解説しました．
2年前には，回文*1であるかを判定するプログラムを作りましたが，これを差し替えて反復語にした理由は，「回文判定ではポインタ変数pに対してp--;としているが，減らす処理というのは，実際にはあまり使われない」と感じたためです．
反復語の判定というのは，例えば「muumuu」とか「わんわんわん」といった文字列についてはYes，「muu」とか「わんわわん」といった文字列についてはNoを出力するというものですが，詳細は，授業ページをご覧ください．
回文にせよ反復語にせよ，初年度に紹介したISBNのチェックデジットにせよ，「入力として与えられた文字列がある条件を満たすか否かを機械で判定する」ための枠組みについては，形式言語理論という分野の中で，これまで深く研究され，「オートマトン」や「文法」として，体系化されてきました．
「条件を満たす文字列の集まり」を「言語」と呼びます．そして，その言語を受理する…入力として与えられた文字列がその言語に属しているとき，かつそのときに限り，「受理する」と判定し，そうでなければ「受理しない」と判定する…機械が構成できるかという問題が考えられてきました．ここで「機械」というのは，今当たり前のように使っているコンピュータも含まれますが，このコンピュータよりも理論的な意味で弱化させたり強化させたりして，そういった理論的な機械で，言語を受理できるかが検討されてきました．
その結果は，コンパイラの構成法，BNF記法，UNIXの正規表現などで，実用されています．
Cで書けるプログラムは，メモリサイズに実際的な上限があるのですがそれを除けば，チューリング機械と同等となります．
なのですが，反復語に限定すれば，UNIXでよく使われる正規表現で実現できます*2．式を書きたいところですが，ちょっと時間がありません．また別の機械wに．
