1

我有点被自动机和语法问题困住了。我搜索了很多，但没有任何成功。

甚至有可能构造一个生成这种语言 L 的语法吗？

 L = { a(2i) | i >= 0}

谁能为我提供简单的解决方案？

4

1 回答 1

6

为这种语言编写语法当然是可能的，但它不会是上下文无关的语法。使用抽水引理很容易证明这一点。

抽水引理指出，对于任何 CFL ，都有一些整数，使得语言中长度至少为 的任何p字符串都可以写为也在语言中。spuvxyzuvxyzvynuvnxynz

也就是说，对于语言中的任何字符串（其长度l大于p），存在一些k这样的语言中存在长度l + nk为任何整数的字符串n。语言不是这种情况，因为这些字符串具有指数长度，所以语言不能是上下文无关的。a2i

为该语言构建一个非上下文无关的语法并不难，但我不知道它有多大用处。

下面是一个 Type 0 语法（即它也不是上下文相关的），但这仅仅是因为产生式用于摆脱元字符。这里的基本思想是，我们在字符串 ( [and ]) 周围放置开始和结束标记，并且我们有一个“复制器”( ↣)，它从左到右移动使a's 加倍；当它到达结束标记时，它要么变成一个返回穿梭（↢），要么它吃掉结束标记并变成一个开始标记破坏者（↞）

Start: [↣a]
↣a: aa↣
↣]: ↢]
↣]: ↞
a↢: ↢a
a↞: ↞a
[↢: [↣
[↞:

于 2014-04-16T04:27:08.760 回答