给定语言的上下文无关文法和pda

Question

我有一种上下文无关的语言，我必须为其创建上下文无关的语法以及下推自动机（确定性或非确定性）。我尝试了不同的生产规则，并使用jflap模拟了它们，但不幸的是未成功。

任何一种指导方针，我们都会感激。

L = { s1@s2@s3@…@sk | k > 1
       ∧ si ∈ {0,1}*
       ∧ ∃i,j i≠j ∧ si=sjR
     }

L中的字符串示例为：{01 @ 10、110 @ 11111 @ 011，...}

Answer 1

正式定义很难解析，但这是我从中得到的：

• 此语言的格式为s1 @ s2 @ s3 ... @ sk
• 每个si是0和1的字符串
• 至少有一对si，sj使得si = sj ^ R

假设这是语言，我们的策略将是先执行第三个条件，然后执行第一个条件，然后执行第二个条件。为了执行第三，我们需要至少输入一对彼此相反的字符串：

S -> 0S0 | 1S1

这为我们提供了wSw ^ R形式的字符串。现在，我们希望能够将其他字符串添加到前面，中间或后面，并以@：

分隔

S -> 0S0 | 1S1
S -> T@S | S@T | @T@ | @

最后，我们需要允许T生成0和1的字符串。

S -> 0S0 | 1S1
S -> T@S | S@T | @T@ | @
T -> 0T | 1T | e

要生成任何语言的字符串：

1. 首先使用第一行中的产生生成一对所需的反向字符串。
2. [使用第二行的第一个产品将其他字符串添加到左侧。
3. 使用第二行的第二个生产线在右边添加任何其他字符串。
4. 使用第二行上的第三和第四个生产线将其他任何字符串添加到中间。
5. 使用第三行中的产生值填充其他字符串。

使用该语言的PDA可以执行以下操作：

1. 循环读取（0 + 1）* @
2. 不确定地跳到假设您已经找到第三个条件所需的第一个字符串的状态
3. 当您跳时，将字符串压入堆栈
4. 再次循环读取（0 + 1）* @
5. 不确定地跳到假设您已经找到第三个条件所需的第二个字符串的状态
6. 当您跳转时，将字符串从堆栈中弹出以进行验证
7. 再次循环读取（0 + 1）* @

您在这里做出两个不确定性的猜测：首先，您将猜测会有相反含义的字符串。其次，您猜您找到了它。如果这两个猜测都是正确的（并且对于该语言中的任何字符串，至少对于k（k + 1）/ 2个猜测中的一对），那么NPDA会接受。