平成23年度 特別 午前 問4

✓ これが正解エ＜letter＞ | ＜identifier＞＜digit＞ | ＜identifier＞＜letter＞

解説

英字で始め、識別子の後ろに英字か数字を足す形です。

日本語で書かれた条件を二つに割るところから始めます。先頭は英字であること。それ以降は英字でも数字でもよいこと。この二つを満たす書き方だけが正解になります。前半の条件から、一文字だけの識別子は英字だけになります。数字一文字をそのまま識別子と認めてしまう定義は、この時点で落ちます。後半の条件からは、再帰の向きが決まります。すでに識別子として認めたものの後ろに一文字だけ足す、という形にすれば、足す一文字は英字でも数字でもよく、先頭は最初に置いた英字のまま変わりません。正解の定義はまさにその形で、英字一文字だけの場合と、識別子の後ろに数字を足す場合と、識別子の後ろに英字を足す場合の三つを並べています。短い文字列で試すと確かめられます。英字一文字は一つ目の場合に当たります。英字のあとに数字が続く二文字は、識別子として認めた英字に数字を足した形です。英字が二つ続く場合も、識別子に英字を足した形で作れます。数字で始まる文字列は、先頭に置けるのが英字しかないので作れません。作ってはいけない文字列を一つ試すのが、この形式言語の問いでは最も速い進め方です。全部の定義を頭から展開しなくても、反例が一つ見つかればその定義はそこで終わりだからです。

ほかの選択肢はなぜ違うのか

• ア＜letter＞ | ＜digit＞ |…：英字一文字と並べて数字一文字も単独で認めているため、数字だけの文字列が識別子になってしまいます。先頭を英字に限るという前半の条件に反します。
• イ＜letter＞ | ＜digit＞ |…：こちらも数字一文字を単独で認めているので、同じ理由で落ちます。英字を左側に足して右へ伸ばす書き方も含みますが、その手前で条件から外れています。
• ウ＜letter＞ | ＜identifi…：後ろに足せるのが数字だけになっているため、英字が二つ続く文字列を作れません。二文字目以降に英字も許すという後半の条件を満たしていません。