離散システム論 「オートマトンと言語理論」レポート課題 このレポート課題は

離散システム論
「オートマトンと言語理論」レポート課題
このレポート課題は、プレイスメントテストに合格した人のためのものです。
（１）プレイスメントテストに合格している人はこのレポートを 7 月 31 日までに提出して
ください。期末試験は受ける必要はありません。
（２）プレイスメントテストに合格しなかった人は、講義の出席点と期末試験によって成績
をつけますので、このレポートを提出する必要はありません。
課題１
正規言語と文脈自由言語の定義を述べ，任意の正規言語は文脈自由言語であることを
示しなさい。
課題２
次の言語に対する文脈自由文法を作りなさい。また、それを受理するプッシュダウンオー
トマトンを作りなさい。
(a) {
0n1n| n ≧ 1 }
(b) a と b の列で、ww という形でないもの（ww は同じ列が二度繰り返されることを表
す）。
課題３
「P＝NP 問題」とは何かを簡単に説明しなさい。
レポート提出はメールで [email protected] へ送ってください。
その際、メールのタイトルは「離散システム論レポート」としてください。
提出してから 3 日以内に「受け取り確認」の返事がないときは、上記アドレスに問い合わせ
てください。