September 2014
Intermediate to advanced
336 pages
7h 53m
Japanese
Content preview from アンダースタンディング コンピュテーション ―単純な機械から不可能なプログラムまで
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
70
3
章 最も単純なコンピュータ
=> #<struct DFADesign
…
>
>>
dfa_design.accepts?('a')
=> false
>>
dfa_design.accepts?('baa')
=> false
>>
dfa_design.accepts?('baba')
=> true
3.2
非決定性有限オートマトン
DFAが理解しやすく実装もしやすいのは、なじみのある機械とよく似ているためです。実際のコン
ピュータにある複雑さをすべて取り除き、使いなれた機械からもっと離れることで、これまでとは異な
る考え方で実験してみましょう。実際のシステムで動かすときの難しさについては、忘れてしまって構
いません。
1つのやり方は、これまでの仮定や制約を少しずつ取り除いていくことです。まず第一に、決定性制
約が制限になっているように見えます。私たちはすべての状態ですべての可能な入力文字に関心があ
るわけではありません。関心のない文字に関する規則をなくしてしまい、想定外のことが起こると機械
は失敗状態になる、と考えるのはどうでしょうか。より風変わりに、機械が矛盾する規則を持つことを
許
して、複数の実行パスを可能にすると、どうなるでしょうか。第二に、これまでは入力ストリームか
ら読んだ文字に応じて状態を変更していましたが、何も読まなくても状態を変更できるとどうなるで
しょうか。
ここでは有限オートマトンの能力に手を加えることで、どんな可能性が新たに切り開かれるのかを見
ていきます。
3.2.1
非決定性
3
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.