順序機械、有限オートマトン、死状態と推移不許可、有限オートマトンの決定性と非決定性、部分集合構成法 普通は、有限オートマトンの状態推移は入力によって起こると考えるので、入力がないときは状態は推移しない（同じ状態にとどまる）ことになるよ。この…

順序機械、有限オートマトン、死状態と推移不許可、有限オートマトンの決定性と非決定性 非決定性有限オートマトンというのは、1つの記号入力に対して複数の状態推移の可能性を持つ機械だったよ。ということはある入力記号列に対して、到達可能となるのは、1…

http://d.hatena.ne.jp/takemita/20061228/p1 http://d.hatena.ne.jp/takemita/20061231/p1 http://d.hatena.ne.jp/takemita/20070101/p2 順序機械の順序機械たる所以は、システムがどの状態のときにどんな入力があると次にどんな状態になるかが決まっている…

http://d.hatena.ne.jp/takemita/20061228/p1 http://d.hatena.ne.jp/takemita/20061231/p1 有限オートマトンで、設計によっては、システムがある（非最終）状態になると、それ以上どんな記号列を入力しても決して最終状態に到達できないという、そういう状…

http://d.hatena.ne.jp/takemita/20061228/p1 前回、順序機械というのをやったよ。システムがどの状態のときにどんな入力があると次にどんな状態になるかが決まっている機械だよ。それのムーア型というのがあったよ。これはシステムの出力が、そのときの状態…

入力と出力のあるシステムを考えるよ。 入力に応じてシステム状態が変わっていくシステムを順序機械というよ。 順序機械は、システムがとりうる状態の集合 、システムが受け取る入力の集合 、システムが行う出力の集合 、どの状態のときにどんな入力があると…

ある言語 が 上の言語であるというのは、言語 が 上のスター閉包 の部分集合であるということだよ。 というのは記号の集合で、 上のスター閉包 というのは、そこに含まれる記号を並べてできるすべての記号列の集合だよ。 記号と記号列は、たとえば単語と文で…