オートマトン (1)
本問を選択
(Select this problem) {
する(Yes)
，しない(No) } No.
Let A be the following automaton.
A = ( { 0, 1, 2, 3, 4 } , { 0, 1 } , δ, 0, { 3 } )
δ(0, 0) = 0, δ(1, 0) = 1, δ(2, 0) = 2, δ(3, 0) = 3, δ(4, 0) = 4, δ(0, 1) = 1, δ(1, 1) = 2, δ(2, 1) = 3, δ(3, 1) = 4, δ(4, 1) = 0 (1) Construct the graph representation (transit diagram) of A.
(2) Explain whether A recognizes (accepts) word 00001010001 or not.
(3) What is the second shortest word automaton A recognizes (accepts).
(4) Construct a regular expression representing the language automaton A recognizes (accepts).
A
は次のオートマトンであるとする。A = ( { 0, 1, 2, 3, 4 } , { 0, 1 } , δ, 0, { 3 } )
δ(0, 0) = 0, δ(1, 0) = 1, δ(2, 0) = 2, δ(3, 0) = 3, δ(4, 0) = 4, δ(0, 1) = 1, δ(1, 1) = 2, δ(2, 1) = 3, δ(3, 1) = 4, δ(4, 1) = 0 (1)
オートマトンA
のグラフ表現(
状態遷移図)
を描け。(2)
オートマトンA
は語00001010001
を認識(
受理)
するかどうか説明せよ。(3)
オートマトンA
が認識(
受理)
する2
番目に短い語は何か。(4)
オートマトンA
が認識(
受理)
する言語を表現する正規表現をつくれ。(
解答は裏面を使用しても構わない．You can use the reverse side of this paper for your answering.)
オートマトン (2)
本問を選択
(Select this problem) {
する(Yes)
，しない(No) } No.
Fig.1 illustrates four lamps and two switches. Switch A flips between its ON and OFF for the leftmost lamp and the third lamp from the left. For example, if switch A is pushed when the leftmost lamp is ON and the third lamp from the left is OFF, then the leftmost lamp changes into OFF and the third lamps from the left changes into ON, and the other lamps have no change. Similarly, all states of lamps except the leftmost lamp change reversely, if switch B is pushed. By using automata, explain that it is impossible to have a configuration in which only the leftmost and the rightmost lamps are ON by pushing switches A and B starting from a configuration in which all lamps are OFF.
図
1
のように4
つの電球と2
つのスイッチA, B
がある.
スイッチA
を押すと、一番左と左から3
番目の電球の
ON/OFF
が逆になる.
例えば,
一番左の電球がついていて(ON)
左から3
番目の電球がついていない(OFF)
ときにスイッチ
A
を押すと一番左の電球が消え,
左から3
番目の電球がつき,
それ以外の電球の状態は変わら ない.
同様にスイッチB
を押すと,
一番左以外の3
つの電球のON/OFF
が逆になる.
すべての電球がついて いない状態からスタートし,
適当にスイッチA, B
を何回か押すことにより,
両端の電球だけつくようにできな いことを,
オートマトンを使って説明せよ.
A B
図
