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.
4.3
プッシュダウン・オートマトンによるパース
125
4.2.2
非等価性
でも待ってください。「3.4 等価性」では、スタックのない非決定的な機械は決定的な機械と能力的
にまったく等価であることを見ました。RubyによるNFAシミュレーションは、入力文字列の文字を読
みながら有限個の「シミュレーション状態」間を移動することで、DFAと同じように振る舞いました。
これによって、任意のNFAを、同じ文字列を受理するDFAに変換することができました。さて、非決
定性は能力を高めてくれるものなのでしょうか。それともRubyのNPDAシミュレーションはDPDAと
同じように振る舞うのでしょうか。任意の非決定性プッシュダウン・オートマトンを、決定性プッシュ
ダウン・オートマトンに変換するアルゴリズムは存在するのでしょうか。
実のところ、そういうアルゴリズムは存在しないことがわかっています。NFAからDFA への変換が
うまくいくのは、取り得る複数のNFA状態を1 つのDFA 状態として表現できるためです。NFAのシ
ミュレーションに必要なのは、現在どの状態にいる可能性があるかを記録し、入力文字を読むたびに
別の取り得る状態の集合を選ぶことだけです。これは適切な規則を与えることで、簡単に実現するこ
とができます。
ところが、これはPDAの場合にはうまくいきません。複数のNPDA 構成を1つのDPDA 構成として
うまく表現できないためです。これは驚くことではありません。問題はスタックにあります。NPDAシ
ミュレー
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.