给定语言的上下文无关语法和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. 使用第三行的production来填充其他字符串

此语言的PDA可以执行以下操作：

循环中的

1. 读取(0+1(*@
2. 不确定性地跳转到一个状态，在该状态下，您假设已经找到了第三个条件所需的第一个字符串
3. 当你跳的时候，把绳子压在绳子上
4. 再次循环读取(0+1(*@
5. 不确定性地跳转到一个状态，在该状态下，您假设已经找到了第三个条件所需的第二个字符串
6. 跳转时，从堆栈中弹出字符串进行验证
7. 再次循环读取(0+1(*@

您在这里进行两个不确定的猜测：首先，您猜测将具有反向的字符串。第二，你猜你找到了它。如果这两个猜测都是对的(它们适用于语言中的任何字符串，至少适用于一对k(k+1(/2的猜测(，那么NPDA接受。