1

标题解释了它。我无法将“方程”的左侧与右侧同步，因为每当我在左侧生成 2 时，必须出现右侧的 2。难道这种语言不是上下文无关的吗？提前致谢！

L = {2^x ∗ 2^y ∗ 2^z = 2^(x+y+z) | x, y, z > 0}

编辑：这与数学方程无关。" *" 和 " =" 只是语言字母表的符号， 2 的 " x" 次方意味着 2 被重复 x 次。

Example of this language:
222*2*22=222222 
2*2*2=222
2*222222*22=222222222
4

3 回答 3

1

使用关于乘法字符串连接和求幂重复的基本事实，我们可以将您的语言重新定义为：

L = { 2^x * 2^y * 2^z = 2^z 2^y 2^x | x, y, z > 0 }

该语言定义可以进一步阐述为：

Lz = { 2^z = 2^z | z > 0 }
Ly = { 2^y * w 2^y | y > 0, w ∈ Lz }
Lx = { 2^x * w 2^x | x > 0, w ∈ Ly }
L = Lx

然后我们可以为 Lz 定义一个文法：

Z   ::=   2 = 2
Z   ::=   2 Z 2

还有一个给 Ly：

{ include Lz's grammar }
Y   ::=   2 * Z 2
Y   ::=   2 Y 2

一个用于 Lx：

{ include Ly's grammar }
X   ::=   2 * Y 2
X   ::=   2 X 2

由于 L = Lx，组合文法的起始符号为X：

于 2017-04-30T16:33:09.437 回答
0

不要让这变得比它需要的更难。您的语言具有以下特点：

  1. =中间有个
  2. LHS 以 s 开头和结尾，中间2有2s 和*s
  3. RHS 只是2s
  4. LHS 和 RHS 上的2s 数量相等
  5. LHS 不包含**.

这些规则很容易放入语法中：

(P1) S -> 2=2
(P2) S -> 2S2
(P3) S -> 2*S2

第一条规则是我们的基本情况，并确定=必须始终将LHSand分开RHS。它还规定LHS必须以 a 结尾，2并且 RHS 必须以 开头2。

第二条和第三条规则允许我们添加更多2的 s 以获得语言中更长的字符串。第二条规则说“你总是可以2在 LHS 的前面放一个，如果你这样做，你必须在 RHS 的末尾放一个”。第三条规则允许我们放入*LHS，只要我们在 RHS 上至少放一个 S”。

你的例子：

222*2*22=222222 
S
2S2                    P2
22S22                  P2
222*S222               P3
222*2*S2222            P3
222*2*2S22222          P2
222*2*22=222222        P1

2*2*2=222
S                 
2*S2                   P2
2*2*S22                P2
2*2*2=222              P3

2*222222*22=222222222
S
2*S2                   P3 
2*2S22                 P2
2*22S222               P2
2*222S2222             P2
2*2222S22222           P2
2*22222S222222         P2
2*222222*S2222222      P3
2*222222*2S22222222    P2
2*222222*22=222222222  P1

该语法的正式正确性证明将涉及证明（a）生成该语言中的每个字符串，以及（2）生成的每个字符串都使用该语言。我们可以同时使用归纳法：

证明：通过归纳。基本情况：语言中最短的字符串是2=2，由 P1 生成。没有更短的生成字符串。归纳假设：假设所有长度小于的字符串k都在语言中生成（集合在长度之前是相同的k）。归纳步骤：我们必须显示长度大于的字符串k也是一致的。如果我们k在语言中有一个长度或更长的字符串（或者，由语法生成），它必须是形式22x22或2*x2，其中x另一个字符串是语言（或者，由语法生成）。的长度x小于k或此参数递归地应用于x自身。由于x长度小于k，归纳假设意味着它可以由语法生成（或者，它在语言中）；并且两种形式都可以生成（或者，在语言中），结果是：通过 P2 的两次应用和 P3 的一次应用（或者，通过语言本身的定义）。

更新：

有一条评论让我注意到，数量*应该固定为 2。这需要更改语法的定义：

S -> 2S2 | 2*R2
R -> 2R2 | 2*T2
T -> 2T2 | 2=2

这以相对较小和可预测的方式改变了上述论点。基本上，我们跟踪 P3 的应用程序的数量，并在第二次之后禁止进一步的应用程序，同时仅在我们看到至少两个应用程序之后才允许消除所有非终结符。

于 2017-05-01T14:13:38.707 回答
-1

这是上下文无关语法的示例，其中 , 等这些字符串222*2*22=222222是2*2*2=222语法的。

<literal>: 2 | <literal>2;
<number>: <literal> | <number>*<number>;
<expression>: <number>=<number>;

使用这些产生式，您想要的字符串都是有效<expression>的。“错误”的字符串也是语法错误的，例如：

22=2

从你的问题中我不清楚这是否是一个问题。我可以想象，您项目中的首要任务是解析字符串而不用担心语义，然后评估语法字符串的语义。

编辑：我很想知道我的回答是否真的有问题，或者我是否刚刚收到“远离我的地盘”的反对票。

于 2017-04-30T17:01:03.743 回答