「オートマトン 言語理論 計算論I」という本(教科書)を読んでいます。
この本には演習問題がついているのですが、本を読んだだけでは解法が分らない上、
答えがついてないため、解けない問題が多く困っています。
(連休明けに試験があり、その範囲なんです。)

ある言語が文脈自由型ででないことを証明したいのですが、
反復補題(パンピングレンマ)を用いて背理法によるのだろうと思うのですが、
どのように仮定するかの方針が立たないのです。

具体的には次のような問題に対し、「…」のような仮定をしてみました。

a){a^i b^j c^k | i<j<k}
  「z=a^n b^(n+l) c^(n+m) (但し、m>l>0)」

しかし、下記のように背理法による矛盾が示せなかったのです。
どこで間違ったのかは分らないので、間違った個所を指摘していただきたいのです。

よろしくお願いします。

「言語を文脈自由言語と仮定する。
nをパンピングレンマの性質を持つ整数とし、
z=a^n b^(n+l) c^(n+m) (但し、m>l>0)とすると、
z∈L かつ |z|≧n が成立する。
したがって、パンピングレンマから
z=u v w x y (ux≠ε、|vwx|≦n)
と表され、かつ
u v^i w x^i y ∈ L
が成立する。
|vwy|≦n なので、vxがaとcの両方を含むことはない。
vxのパターンにより次の2つの場合を考える
(i)vxが一種類の文字だけからなる場合

(ii)vxが2種類の文字からなる場合」

ここまで書いたところで、
v=b、x=c
とすると、例えば、
u=a、w=bb、y=ccc
の場合を考えると、矛盾が導けないことに気付きました。

このQ&Aに関連する最新のQ&A

A 回答 (1件)

連休明けに試験があるとのことで,もう手遅れかもしれませんが...



パンピングレンマですが,

z = uvwxy

となるu,v,w,x,yが1つは存在する,というものと思われます(あまり詳しくないです).

unicorn01さんが仮定したz=a^n b^(n+l) c^(n+m)に対して,v=bとなるものが存在するかというと,必ずしもそうではないのではないでしょうか.

実際,z=a^n b^(n+1) c^(n+2)に対して,v=bというものは存在しないですね.iが0の時にLに属さなくなりますので.
    • good
    • 0
この回答へのお礼

ありがとうございました。 そのとおりでした。
あとで気づいたのですが、自己レスつけれないので困ってたんです。
また何かありましたらよろしくお願いします。

(質問した段階ではパンピングレンマによる証明方法を勘違いしてました。)

お礼日時:2001/05/11 19:30

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aと関連する良く見られている質問

Q不斉炭素は炭素n個につき2のn乗個、光学異性体を持ちますが、異性体の表記がD、L、メソしかないのですが

よろしくお願いします。
表題の通りなのですが不斉炭素は炭素n個につき2のn乗個、
光学異性体を持ちますが、異性体の表記がD、L、メソ体の
三種しかありません。

たとえば不斉炭素3つで8個、異性体がある場合はどのように
表記をするのでしょうか?

ご教授よろしくお願いします。

Aベストアンサー

もっとも一般的なものはR,S表示法です。
個々の不斉炭素について、その立体配置がRであるかSであるかを判断します。したがって、何個不斉炭素があっても問題はありません。

DL表示法は、糖やアミノ酸など限定された範囲内で使用されることが多く、一般の有機化合物における不斉炭素の表示法としては不適当です。

ややこしい話をしますと、不斉炭素をもたない光学活性物質というのも存在します。そちらになると幾分厄介になりますが、高校レベルでは関係ありませんね。

Q|記憶装置とストレィジとdATABASE|

|記憶装置とストレィジとdATABASE|
|これらについて説明してください|
|質問するのは自分が大卒なのに正直まったく理解できていないと感じてはいませんが他者にはそう見える面を改善するためですもしくは修正するためあるいは修整目的です|
||
|本音を言うと地道に一人でシコシコ勉強してもちっともはかどらないので公に問うているのです|
|文章の末尾|

Aベストアンサー

> ファイルシステムはデータベースと似ている

データベースはファイルシステムを使いますが、ファイルシステムだけではデータベースにはなりません。
ファイルシステムだけでは、ファイル名でファイルを読みだすくらいですが、データベースはたとえば特定の条件を満たすデータだけを拾い出す、などいろいろなことができます。データベースでどんなことができるかは、ここで述べるのは大変です。これに関してはデータベースの本を読むとかgoogleで検索されるとか、参考のURLをご覧になるとかされたらいかがでしょうか?

参考URL:http://ja.wikipedia.org/wiki/%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9

QAC電源(L,N.E)の特性

AC100V電源のL, N, Eの特性について、以下質問いたします。

(1) AC電源を使う機器の場合、ヒューズはL側に入れるのはなぜでしょうか?
N側に入れても、電流はLとNに同じだけ流れるので、問題ないと思うのですが。

(2)100Vを、Nを使わず、LとEから取るとどのような問題があるでしょうか?

(3)そもそも、Eが接地されているのに、Nも接地されているのはなぜでしょうか?
両方接地されていないと、感電防止?にならないのでしょうか?

Aベストアンサー

(1)L側は、100Vの電圧が加わっており、N側は0Vです。もし、N側にヒューズを入れ、このヒューズが切れてしまっても、L側は100Vとつながったままですので、事故が起きているのに危険な状態のままになっています。L側にヒューズを入れておけば、過電流などにより事故が起きてもN側は、0Vなので危険はありません。

(2)Nは接地側電線、Eは接地電線で、似てるようで違います。基本的にEは、機器と地面、Nと地面がつながっていますが、電流は流れません。なぜなら、たとえば、機器の筐体(ケース)などにEをつなげますが、ここには電気が流れる経路がないからです。もし、ここに電気が流れてしまうことがあれば、それは漏電という事故になります。
機器-アースー地面-N側という経路に電気が流れてしまいます。
したがって、EをNの代わりに使うことはできません。
電流は、Lから機器をとおり、Nの線から戻るので安全ですが、電流がLからEに流れてしまうと、人体や機器のケース、建物など、流れてはいけないところに電流が流れることになるので、感電や火災などの事故になり危険になります。
漏電で流れてしまう場合は、電流が微量であったり、漏電遮断器がすぐに作動するするため、危険は回避されます。

(3)ほぼ、(2)と同じ回答になるかと思います。
機器(負荷)だけが接地され、地面につながっていても、万が一、漏電が起こったときに電流の逃げる道(Nに戻る道)がないため、人体に電気が流れてしまい、危険な状態となってしまいます。普通は、人体より地面のほうが抵抗が小さいので、人間はほとんど感電せずにすみます。

(1)L側は、100Vの電圧が加わっており、N側は0Vです。もし、N側にヒューズを入れ、このヒューズが切れてしまっても、L側は100Vとつながったままですので、事故が起きているのに危険な状態のままになっています。L側にヒューズを入れておけば、過電流などにより事故が起きてもN側は、0Vなので危険はありません。

(2)Nは接地側電線、Eは接地電線で、似てるようで違います。基本的にEは、機器と地面、Nと地面がつながっていますが、電流は流れません。なぜなら、たとえば、機器の筐体(ケース)などにEをつなげます...続きを読む

Qz=cos(xy)のグラフ

xとyが独立変数のとき、z=cos(xy)のグラフを書こうとしています。
wxmaximaのプロット(3次元プロット)の関数にcos(xy)と入力しましたところ、

plot3d: expected <expr. of v1 and v2>, [v1, min, max], [v2, min, max]

というエラーがでました。

エラーの意味もよくわからないのですが、
とりあえず出来ることとしてマクローリン展開しようとしましたら、
原点での(高次?高階?)偏微分係数が全てゼロ、すなわち

f_x(0,0)=f_y(0,0)=f_xx(0,0)=f_xy(0,0)=f_yy(0,0)=・・・=0

ですので、

cos(xy)=1+0+0+・・・

としか表せません。

これって変だよな?って思うんですけど。
どこか間違っているのでしょうか?

簡単な関数なので、すぐい書けるだろうと思っていたのですが、うまくいきません。
お分かりになる方、いらっしゃいましたら、何卒、ご教授くださいませ☆

Aベストアンサー

あなたは本当に高次の偏微分をやってみたのですか?
少し計算すればわかるのですが、もっと計算すれば偏微分係数が"0"にならないものが出てきます。

f_xyxy(0,0)を実際に計算してみましょう。

cos(x)のマクロ―リン展開
cos(x)=1-x^2/2!+x^4/4!-...
ですから
cos(xy)=1-(xy)^2/2!+(xy)^4/4!-...
となります。つまり、4n次の項しか出てこないのです。1,2次程度で計算で結論を出してはいけません。

Q流体に使う単位、N/ml 。その「N」は何?

流体に使う単位、N/ml 。その「N」は何?
教えてください。

Aベストアンサー

補足です。

SI単位導入後は"N"(ノルマル)は使用禁止らしいです。

参考URL:http://www.ryutai.co.jp/shiryou/gas/gas-qtani.htm


人気Q&Aランキング

おすすめ情報