九州大学システム情報科学府情報理工学専攻 2016年8月実施オートマトンと言語

Author

Zero

以下の状態遷移図を持つ有限オートマトンに対し，次の各問いに答えよ．ただし，は，それぞれ状態の集合，アルファベット，遷移関数，初期状態，最終状態の集合を表し，とする．

(1) が受理する長さ以下の文字列をすべて列挙せよ．

(2) が受理する言語をで表す．を受理する状態数最小の決定性有限オートマトンの状態遷移図を与えよ．

(3) を，状態を通らずにによって受理される文字列からなる言語とする．を表す正規表現を１つ与えよ．

を終端記号の集合とする２つの文脈自由文法 , を考える．ただし，, , は，それぞれの非終端記号の集合，生成規則の集合，開始記号である．また，, , は，それぞれの非終端記号の集合，生成規則の集合，開始記号である．文脈自由文法が生成する言語をと表す．次の各問いに答えよ．

(1) が生成する長さ 3 の文字列をすべて列挙せよ．

(2) 言語を説明せよ．

(3) が生成する長さ 4 の文字列をすべて列挙せよ．

(4) 言語を説明せよ．ただし，集合について，とする．