0

我有一个问题说:

构造一个接受语言 {a^ib^j | 的 PDA 0 <= 我 <= j}

这是给定的解决方案:

  δ ( q0, a, z ) = ( q0, az )   read a, push a
  δ ( q0, a, a ) = ( q0, aa )
  δ ( q0, b, a ) = ( q1, λ )   read b, pop a
  δ ( q1, b, a ) = ( q1, λ )
  δ ( q1, λ, z ) = ( qf, z )   end of string, stack empty
  δ ( q1, b, z ) = ( q1, z )   check the additional b’s 

但据我了解,一个可能的输入字符串会以 b 开头,因为 i 可能是 0 而 a^i 可能是 1,而 j 可能是 1 而 b^j 可能是 b,这是否意味着应该有一行说的是:

δ (q0, b, z) = (q1, z) ?

还是我误解了什么?

4

1 回答 1

0

是的你是对的。

实际上上面的 PDA 接受 {a^ib^j | 1 <= 我 <= j}

于 2015-12-08T05:25:45.413 回答