問 題
S，A，B を非終端記号（S は開始記号），_ を終端記号，Tnum，Teng を終端記号の集合とする文脈自由文法 G について考える。Tnum={0，1，2，…，9} （数字の集合），Teng={a，b，c，…，z}（英小文字の集合）であり，G の生成規則は次のとおりである。
・S → A
・S → B
・A → aS ・A → a ・A → _S（ただし，a は終端記号で，a ∈ Tnum）
・B → bB ・B → b ・B → _B （ただし，b は終端記号で，b ∈ Teng）
例えば，「2020」という文は，「S ⇒ A ⇒ 2S ⇒ 2A ⇒ 20S ⇒ … ⇒ 202A ⇒ 2020」のように生成でき，「tokyo_olympic」という文も，「S ⇒ B ⇒ tB ⇒ toB ⇒ … ⇒ tokyoB ⇒ tokyo_B⇒ tokyo_oB ⇒ … ⇒ tokyo_olympiB ⇒ tokyo_olympic」のように生成できることから，いずれもG により生成される文である。
このとき，㋐～㋓のうち，G により生成される文として妥当なもののみを全て挙げているのはどれか。
㋐ tokyo_2020
㋑ 2020_olympic
㋒ 1st_prize
㋓ 42_point_195_kilometers
1．㋐，㋑
2．㋐，㋑，㋓
3．㋐，㋒
4．㋑，㋒
5．㋑，㋒，㋓
解 説
例をじっくり読んだ上で、選択肢を見ると 「文字＿数字」、「数字＿文字」、「数字文字」 を それぞれ作ることができるかどうかがポイントです。
規則は「数字＿文字」だけでなく「数字文字」も作れます。（S→A→2S→2B→2b といった流れです。）しかしいったん文字を生成し始めると、ルールから S に戻れない → 数字を作れない とわかります。この規則をふまえて選択肢を検討します。
㋐ですが
tokyo_2020 は、文字→数字の順なので作れません。
㋑、㋒は妥当です。
2020_olympic は、例の202Aから、202A→2020S→2020A→2020_S→以下tokyo の例と同じ流れで作ることができます。また 1st_prize も作れます。
㋓ですが
文字→数字の順が含まれるため作れません。
以上より、選択肢 4 が正解です。
コメント