5

たとえば、バランスの取れた括弧と角かっこ（[] []）を受け入れるPDAを設計するにはどうすればよいでしょうか。始めるのに苦労しています。この問題の遷移関数を書くのに助けが必要です。どんな助けでも大歓迎です

4

2 に答える 2

9

私は通常、誰かの宿題全体を彼らのために行うことはありませんが、実際には、オートマトンに関しては、たとえ私が行ったとしても、これらのことがどのように機能するかを本当に理解していない限り、それはあまり役に立ちません。学校はそもそも彼らにうまく教えていません。

このPDAがどのように動作するかを考えて、状態や遷移などを今のところ忘れましょう。PDAが入力を受け取ると、次のように機能するはずです。

  • 入力がない場合：
    • スタックの最上位が空の場合（この例では、特別な値で示されることがよくあります$）、PDAは文字列を受け入れます。これは、適切にバランスの取れた括弧と括弧の文字列です。
    • それ以外の場合は、エラー状態になります。文字列は、括弧と角かっこの適切にバランスの取れた文字列ではありません。
  • 入力がan(またはaの場合は[、入力をスタックにプッシュして、次の入力文字を確認します。
  • 入力が)thenの場合：
    • スタックの一番上がポップである場合は、スタック(の一番上をポップし、次の入力を確認します。
    • それ以外の場合は、エラー状態になります。文字列は、括弧と角かっこの適切にバランスの取れた文字列ではありません。
  • 入力が]thenの場合：
    • スタックの一番上が[ポップである場合は、状態の一番上で、次の入力を確認します。
    • それ以外の場合は、エラー状態になります。文字列は、括弧と角かっこの適切にバランスの取れた文字列ではありません。

ここで、PDAが何をしなければならないかを知って、PDAをより正式に説明する方法を考えてみましょう。私たちはそれを仮定します：

  • 有効な入力記号のセットΣ={ (、、、)および}[]
  • 初期スタックシンボルZ=$
  • 有効なスタックシンボルのセットΓ={ (、[} ∪Z
  • 状態のセットQ={q0、ACCEPT、REJECT}
  • 初期状態q0。

http://en.wikipedia.org/wiki/Pushdown_automatonで説明されているものと同様の表記法をPDA状態遷移に使用して、状態と物事の流れについて考えることができます。

  • （q0、ε、top = $、ACCEPT、nil）これはPDAに通知します。状態q0にあり、入力がなく、スタックの最上位が$ACCEPT状態になり、スタックは変更されません。

  • （q0、ε、top = (、REJECT、nil）これは、PDAに通知します。状態q0にあり、入力がなく、スタックの最上位が(REJECT状態になり、スタックは変更されません。

  • （q0、ε、top = [、REJECT、nil）これは、PDAに通知します。状態q0にあり、入力がなく、スタックの最上位が[REJECT状態になり、スタックは変更されません。

  • （q0、(、top = top、q0、push (）これはPDAに通知します。状態q0にあり、入力が(thenの場合、スタックの最上位にあるものに関係なく、状態q0に移動してa(をプッシュします。スタック。

  • （q0、[、top = top、q0、push [）これはPDAに通知します。状態q0にあり、入力が[thenの場合、スタックの最上位にあるものに関係なく、状態q0に移動してa[をプッシュします。スタック。

  • （q0、)、top = (、q0、pop）これは、PDAに通知します。状態q0にあり、入力がa)で、スタックの最上位がaの(場合、状態q0に移動し、スタックの最上位をポップオフします。 。

  • （q0、)、top = [、REJECT、nil）これはPDAに通知します。状態q0にあり、入力がa)で、スタックの最上位が[REJECTスタックに移動し、スタックは変更されません。

  • （q0、)、top = $、REJECT、nil）これはPDAに通知します。状態q0にあり、入力がa)で、スタックの最上位が$REJECTスタックに移動し、スタックは変更されません。

  • （q0、]、top = [、q0、pop）これは、PDAに通知します。状態q0にあり、入力がa]で、スタックの最上位がaの[場合、状態q0に移動し、スタックの最上位をポップオフします。 。

  • （q0、]、top = (、REJECT、nil）これはPDAに通知します。状態q0にあり、入力がa]で、スタックの最上位が(REJECTスタックに移動し、スタックは変更されません。

  • （q0、]、top = $、REJECT、nil）これはPDAに通知します。状態q0にあり、入力がa]で、スタックの最上位が$REJECTスタックに移動し、スタックは変更されません。

より多くの状態を使用してこれを達成することもできましたが、1つの「処理」状態で十分であることに注意してください。

また、インストラクターによっては、REJECT状態を明示的に追加する必要がない場合もありますが、そうすることをお勧めします。

これがお役に立てば幸いです。

于 2012-11-19T01:13:33.880 に答える
3

これはあなたが始めるのを助けるかもしれません：

bool check_and_pop(char c) {
  if (top() == c) {
    pop();
    return true;
  }
  return false;
}

int check_input() {
 char c;
 while ((c = getc())) {
  switch (c) {
    case '(': case '{': case '[': push(c); break;
    case ')': 
      if (!check_and_pop('(')
       return REJECT;
      break;
    case '}':
      if (!check_and_pop('{')
       return REJECT;
      break;
    // ...
 }
 // end of input, check the stack to accept/reject
 if (stack_size() == 0)
    return ACCEPT;
 else
    return REJECT;
}
于 2012-11-19T00:37:37.863 に答える