講演抄録/キーワード |
講演名 |
2013-12-20 09:30
文脈自由言語の決定問題”L(G)=Σ* ?”, 再考 ○田中榮一 COMP2013-38 |
抄録 |
(和) |
“文脈自由文法Gが全ての終端記号列を生成するか”という決定問題は決定不能であると考えられてきた.この問題が決定可能であることを証明した.このことから,チューリング機械の停止問題2,準‐Thueシステムの決定問題,ポストの対応問題は決定可能である. |
(英) |
The decision problem "whether a context free grammar G generates all terminal strings or not" has been considered to be undecidable. We prove that this decision problem is decidable. Therefore, the 2nd halting problem of a Turing machine, the decision problem of a semi-Thue system and Post's correspondence problem are decidable. |
キーワード |
(和) |
文脈自由言語 / 決定問題 / ゲーデル / 停止問題 / チューリング機械 / / / |
(英) |
Context Free Language / Decision Problem / Godel / Halting Problem / Turing Machine / / / |
文献情報 |
信学技報, vol. 113, no. 371, COMP2013-38, pp. 1-6, 2013年12月. |
資料番号 |
COMP2013-38 |
発行日 |
2013-12-13 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2013-38 |