首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >让Σ={ a;b}我如何在JFLAP中定义一个可以识别以下内容的PDA?

让Σ={ a;b}我如何在JFLAP中定义一个可以识别以下内容的PDA?
EN

Stack Overflow用户
提问于 2018-04-01 17:03:35
回答 1查看 104关注 0票数 0

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

例如: abb是L的元素,abbb是L的元素,ε是L的元素,但是babbb不是L的元素,abbb不是L的元素

EN

Stack Overflow用户

发布于 2018-08-25 05:00:13

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

  1. asL
  2. asb中,L
  3. asbbL

我们可以将这些观察结果结合起来,得到一个上下文无关的语法:

代码语言:javascript
运行
复制
S := aSbb | aSb | aS | e

根据我们的观察,这个语法生成的每个字符串都必须是L格式的。为了证明这是一种用于L的语法,我们必须证明可以生成L中的任何字符串。要获取字符串a^n b^k,我们可以执行以下操作:

  1. use rule #1 code x times
  2. use rule #2 code y times
  3. use rule #3 code z times
  4. 确保x + y + z = n
  5. ensure y + 2z = k

设置y = k - 2z并替换,我们得到x + k - 2z + z = n。重新排列:

如果选择k > n,则可以选择zx,只要选择n - k = x - z.

  • If z,就可以选择zx。只要选择k = n,请注意,我们不妨选择

请注意,在上面的示例中,我们总是可以选择zx,因为它们是0 <= x, z <= n0 <= k <= 2n

票数 0
EN
查看全部 1 条回答
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/49596481

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档