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.
110
4
章 能力を高める
4.1.2
規則
バランスのとれた括弧のDPDAにあるアイデアは直感的でわかりやすいのですが、これを実際に構
築するとなると、解決すべきやっかいな技術的詳細があります。まずはプッシュダウン・オートマトン
の規則がどのように動くべきか、正確に決める必要があります。ここには設計上の問題がいくつかあり
ます。
●
すべての規則がスタックを変更したり、入力を読んだり、状態を変更したり、あるいはこれらす
べてをやる必要があるのか。
●
プッシュする規則とポップする規則、2種類の規則が必要になるのか。
●
スタックが空のときに状態を変更する特殊な規則は必要か。
●
NFAの自由移動のように、入力を読まずに状態を変更してもよいか。
●
そのようにDPDAが自発的に状態を変えられるとしたら、「決定的」というのは何を意味するのか。
必要なものをすべてサポートできる、柔軟性のある規則のスタイルを1つ選ぶことによって、こうし
た疑問すべてに答えることができます。PDA 規則を5 つの部分に分割してみましょう。
●
機械の現在の状態
●
入力から読む必要のある文字（オプション）
●
機械の次の状態
●
スタックからポップする必要のある文字
●
スタックのトップにある文字をポップした後、スタックにプッシュする文字のシーケンス
最初の3つはDFAとNFA の規則に似ています。状態を変える必要のない規則の場合、次の状態は
現在の状態と同じになります。入力を読む必要がない規則の場合（すなわち、自由移動）、機械が非決
定的
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.