正規言語に対する繰り返し定理による証明

質問

正規言語に対する繰り返し定理による証明

L={w|wは0と1を同じ個数含む}とする。
Lが正規言語でないことを、繰り返し定理を用いて証明せよ。

【繰り返し定理】
1.|y|>0
2.|xy|≦n
3.∀i≧0,xy^izはLの部分集合

言語Lが正規言語であると仮定すると、Lに対して繰り返し定理が成立する。
Lに属する語A=w(wは0と1をn個ずつ含む)をとると、|A|=2n≧nであるから、定理の条件を満たすようなAの分解A=xyzが存在する。

この後をどうすればよいのかが分かりません。
yが
(0の個数)=(1の個数)のとき
(0の個数)>(1の個数)のとき
(0の個数)<(1の個数)のとき
で場合分けをすればいいとは思うのですが・・・
どう矛盾を導きだせばいいのかが分かりません。
ご教授願います。

回答No.1

Tacosan

とりあえず, 「繰り返し定理」をきちんと正確に理解してください.