文脈自由文法をチョムスキー標準形に変換

質問

大学の数学で分からない問題があります。
どなたか教えていただけないでしょうか？

１．次の規則を持つ文脈自由文法をチョムスキー標準形に変換せよ。
(1) G=({S,A},{ab},P,S)
P={S→Ab,A→aAb,A→ab}
(2) G=({S,A,B},{ab},P,S)
P={S→aB,S→bA,A→a,A→aS,A→bAA,B→b,B→bS,B→aBB}
(3) G=({S},{a,b},P,S)
P={S→aS,S→aSbS,S→ε}

２．次の書き換え規則で定義される文法が生成する言語を示せ。
　　但し、「={S,A,B},Σ={0,1,2},開始記号はSとする。
(1) S→0AB,A→0AB|0B,B→1
(2) S→S0|AB,A→1A|1,B→2
(3) S→A,A→0A|0,B→B1|1
(4) S→AB.A→0A1|01,B→B2|2

問題は以上です。長くなってしまい申し訳ありません。
また、学校で何やっていたんだとお怒りの方もいらっしゃるかと思いますが、何卒よろしくお願いします。

回答No.1

A-Tanaka · ベストアンサー

こんばんは。

解き方のヒントは、次の資料を参考になさるとよいでしょう。
http://www.trs.cm.is.nagoya-u.ac.jp/~sakai/lecture/automata/slide14-handout.pdf

ただし、上の資料では何のことやら・・ということであれば、次の資料にあるように、一般記号を簡便にして、解いてみればよいかと思います。
http://www.jaist.ac.jp/~kshirai/lec/i223/03.pdf

お礼

A-Tanakaさん、早速のご回答ありがとうございます。
教えていただいた資料をもとに、頑張って解いてみようと思います。
分からないことがあったときはまた質問させていただくかもしれませんが・・。
本当にありがとうございましたm(_ _)m