我有一个问题说:
构造一个接受语言 {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) ?
还是我误解了什么?