string - 使用 PDA，证明 ( x * y ) + x 是一个有效的字符串

Question

如果你能帮助我并解释它是如何完成的，我在 C 部分遇到了麻烦。提前谢谢你！

标签： stringmathlogicdiscrete-mathematicspushdown-automaton

Answer 1

(a) 据我所知，他们只是要求重写语法：

<E> -> <E> + <T>
<E> -> <E> - <T>
<E> -> <T>
<T> -> <T> * <F>
<T> -> <T> / <F>
<T> -> <F>
<F> -> (<F>)
<F> -> x
<F> -> y

(b) 他们想要 (x * y) + x 的推导：

                          (             <T> -- <F> -- x
                         /             /
                        /             /
                       /             /
      <E> -- <T> -- <F> -- <E> -- <T> -- *
     /                 \             \
    /                   \             \
   /                     \             \
<E> -- +                  )             <F> -- y
   \
    \
     \
      <T> -- <F> -- x

(c) 我们可以定义一个 NPDA，它不确定地将所有有效的派生推入堆栈，然后弹出输入以接受。堆栈看起来像这样：

stack         input remaining
Z             (x * y) + x
<E>Z          (x * y) + x
<E>+<T>Z      (x * y) + x
<T>+<T>Z      (x * y) + x
<F>+<T>Z      (x * y) + x
(<E>)+<T>Z     x * y) + x
<E>)+<T>Z      x * y) + x
<T>)+<T>Z      x * y) + x
<T>*<F>)+<T>Z  x * y) + x
<F>*<F>)+<T>Z  x * y) + x
x*<F>)+<T>Z    x * y) + x
*<F>)+<T>Z       * y) + x
<F>)+<T>Z          y) + x
y)+<T>Z            y) + x
)+<T>Z              ) + x
+<T>Z                 + x
<T>Z                    x
<F>Z                    x
xZ                      x
Z                 (empty)