生成上下文无关语法，其中第 i 个字符与 i+3 处的字符匹配

Question

我在生成上下文无关语法时遇到问题，其中字符为 0 或 1，并且位置 i 处的符号与位置 i+3 处的符号相同，并且字符串大于 4。 L : {x ∈ {0, 1}* |位置 i 处的符号与位置 i+3 处的符号相同，|x| ≥ 4}

我能够生成所有 4 个字符长的字符串来遵循该语言，但当长度为 4 时我无法超越

Answer 1

以下语法符合您的描述：

S -> D* A D D A D*
S -> D* B D D B D*

D -> 0
D -> 1

A -> 0
B -> 1

本质上，语法强制在某个位置

i

处的数字等于

i + 3

处的符号。请注意，这是通过要求匹配的字符串包含

A D D A

或

B D D B

来完成的。令该子序列中第一个符号匹配的符号位于位置

i

，则后面 3 个符号 (

i + 3

) 必须是相同的符号。

由于其余符号没有受到任何限制，因此它们都是

D

，这意味着在这种情况下可以是任何数字。

由于子序列的大小为

4

，并且可以在其前面或后面固定任何数字，因此语法符合长度要求。正式表述为

|x| ≥ 4

。