grammar - 不受限制的语法

Question

这个通用语法有什么作用？

S -> LR 
L -> L0Y 
L -> LX 
X1 -> 1X 
X0 -> 0X 
X0 -> 1Y 
Y1 -> 0Y 
YR -> R     
L  -> epsilon 
R  -> epsilon

开始符号是 S。我试图从这个语法生成字符串，我得到了每个二进制数。但我认为它做了一些具体的事情。

Answer 1

S -> LR 
L -> L0Y 
L -> LX 
X1 -> 1X 
X0 -> 0X 
X0 -> 1Y 
Y1 -> 0Y 
YR -> R     
L  -> epsilon 
R  -> epsilon

终端：0,1 开始：S

让我们拆分语法：

S -> LR 
L -> L0Y 
L -> LX

这将生成一个形式为 ,和,的L字符串。X0YR

X1 -> 1X 
X0 -> 0X 
X0 -> 1Y 
Y1 -> 0Y 
YR -> R

X将and视为Y作用于二进制字符串：X将向右传播，然后将 a 更改0为1和所有后续1的 s 到0s。实际上，单次X递增二进制数而不改变其字符串长度（或卡住）。

前导Y会将所有 s 的字符串重写1为所有0s（或卡住）。

将规则L视为字符串右侧部分的可能操作。L => L0Y会将字符串从全1重置为全零，并将其长度增加一。L => LX将增加任何其他数字，但如果该值处于最大值则失败。

这两个动作一起足以（低效地）生成所有 0 和 1 的字符串（包括空字符串）。

L  -> epsilon 
R  -> epsilon

只会清理哨兵。

用四个词对语言进行一种可能的描述：

所有字符串的集合