4

明日の試験と教授は、その上にある質問を教えてくれます:)。

この図のコンテキストでは、L はイプシロン (空の文字列) であり、Z0 はスタックの空のシンボルです。

私は言語が生成する単語に関するいくつかのルールを決定する上である程度の進歩を遂げましたが、言語全体を特定することはできませんでした.

ありがとう！

PDA ダイアグラム

4

3 に答える 3

4

This PDA is not nearly as non-deterministic as it appears at first glance... Consider the following cases.

  1. Suppose the input starts with ab. Then we go to state 2 with an empty stack, so the "L" rule does not match, so we are only in state 2.

  2. Suppose the input starts with (a^n)b for n > 1. Then we go to state 2 with a^(n-1) on the stack, and the "L" rule triggers taking us back to state 1 with a^(n-2) on the stack. But since the stack in state 2 is a^(n-1) (and n>1), the loop-back arrows on state 2 cannot match... So here again, we are (effectively) only in one state: state 1.

  3. Suppose the input starts with ba. Then again we go to state 2 with an empty stack, and as in case (1), the "L" rule does not match so we are only in state 2.

  4. Finally, suppose the input starts with (b^n)a for n > 1. Then we go to state 2 with with b^n on the stack, so the "L" rule does not trigger and we are only in state 2.

In other words, any time the "L" rule creates a "fork" of the PDA into state 1, it only does so because "a" was on top of the stack... Which implies that the fork remaining in state 2 must die on the very next input symbol. So in effect there is no non-determinism here, and you can model this PDA as if it is always in just one state.

With this observation in hand, I think it is pretty easy to see that @Nayuki is correct: This PDA accepts any string with twice as many a's as b's.

First, show that when the PDA is in state 1, the stack always consists entirely of a's or entirely of b's (or is empty). And when the PDA is in state 2, the stack consists entirely of b's (or is empty). This is a simple case analysis similar to the four cases above; e.g. "state 1, stack=a^n, next character b => state 1, stack=a^(n-2)". (Taking care for the cases of n=0 or n=1.)

Think of each b as "wanting to be partnered with 2 as". State 1, stack=a^n means n as are waiting for partners. State 1, stack=b^n means n bs are waiting for partners. State 2, stack=b^n means one b was partnered with one a and n bs are still waiting for partners.

Prove that what I just wrote is true, and the result follows.

于 2011-08-11T02:06:11.940 に答える
2

頭の中でいくつかのテストケースを試してみて、厳密には何も証明していませんが、入力文字列に b の数と比較して a の数が 2 倍ある場合にのみ、この (非決定論的) PDA の受け入れ可能な計算が存在すると思います。

于 2011-08-10T22:00:15.703 に答える
1

「a」の数は「b」の数の2倍です。

正確な文法：

S  = (a|b)*      where N_a(S)=2*N_b(S)

N_a（X）は、X内の「a」の数などを意味します。

どの時点でも、スタックはすべて「a」またはすべて「b」のいずれかになります。なんで？なぜなら、a/xxbxxまたはb/xxaxxの遷移がないからです。

ケース1：スタックはすべて「a」です。

サイクルは次の形式になります。

  1. a（a * b）+、最後の場合、（2-> 1）で遷移L、a/Lを取得します

  2. a（a * b）+ a、最後の場合、（2-> 1）で遷移a、Z0/Z0を取ります。最後の「a」はスタックから何もポップしません。

各サイクルで、ポップされる「a」の数は2つです。サイクル数は「b」の数と同じです（最後にa、Z0 / Z0が発生した場合を除く）

'a'の数が最後の'b'の前にある場合は、最後の遷移L、a/Lを取得します

'a'の数が最後の'b'の前に奇数である場合、最後の遷移a、Z0/Z0を取ります。a、Z0/Z0はもう1つ「a」を受け入れます

したがって、

A1=a(a*b)+a  where N_a(A1)=2*N_b(A1),     N_a(A1) is even
A2=a(a*b)+   where N_a(A2)=2*N_b(A2),     N_a(A2) is even

これは次のようになります。

A=a(a|b)+    where N_a(A)=2*N_b(A),     N_a(A) is even

（状態1になり、スタックは空になります）

ケース2：スタックはすべて「b」です。

同様に、各サイクルがb * ab*aの形式になることがわかります。そして、各サイクルで、正確に1つの「b」がポップオフされます。'b'が受け入れられると、'b'がスタックにプッシュされます。したがって、スタックが空で、状態1に戻ると、サイクルが実行される回数は、受け入れ/スタックにプッシュされた'bの数に等しくなります。したがって、

B=b(b*ab*a)^n where N_b(B)=n

しかし、ご覧のとおり、n = N_a（B）/2です。したがって、

B=b(b*ab*a)+ where N_a(B)=2*N_b(B)

これは次のようになります。

B=b(b|a)+ where N_a(B)=2*N_b(B)

また、可能なパスは2つ（AまたはB）のみであり、サイクルは0回または1回実行できるため、

したがって、

S=(A|B)*
A=a(a|b)+    where N_a(A)=2*N_b(A)
B=b(b|a)+    where N_a(B)=2*N_b(B)

これは次のようになります。

S=((a|b)+)*   where N_a(S)=2*N_b(S)

これは次のようになります。

S=(a|b)*      where N_a(S)=2*N_b(S)

QED

于 2011-08-11T00:07:16.900 に答える