formal-languages - 让 Σ = { a; b} 如何在 JFLAP 中定义一个识别以下内容的 PDA？

Question

L = {a^nb^k | 2n >= k}

例如：abb是L的元素，aabbb是L的元素，ε是L的元素，但是babbb不是L的元素，abbb不是L的元素

Answer 1

中最短的字符串L是空字符串，e。给定语言中的字符串s，以下规则成立：

1. as在L
2. asb在L
3. asbb在L

我们可以结合这些观察得到一个上下文无关的语法：

S := aSbb | aSb | aS | e

根据我们的观察，该文法生成的每个字符串都必须在L. 为了证明这是 的语法L，我们必须证明L可以生成任何字符串 in 。要获取字符串a^n b^k，我们可以执行以下操作：

1. x多次使用规则#1
2. y多次使用规则#2
3. z多次使用规则#3
4. 确保x + y + z = n
5. 确保y + 2z = k

设置y = k - 2z和替换我们发现x + k - 2z + z = n. 重新排列：

1. if k > n, thenz和x可以任意选择，只要k - n = z - x.
2. if k < n, thenz和x可以任意选择，只要n - k = x - z.
3. 如果k = n，观察我们不妨只是选择y = n。

请注意，我们始终可以在上面的示例中选择z和，因为和。x0 <= x, z <= n0 <= k <= 2n