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形式的字符串，X和0Y的字符串，R。

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

将X和Y视为作用于二进制字符串:X将向右传播，然后更改0 到 1 以及所有后续的 1 到 0。实际上，单个 X 会递增二进制数而不改变其字符串长度(或卡住)。

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

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

这两个操作一起足以生成(低效)所有零和一的字符串(包括空字符串)。

L  -> epsilon 
R  -> epsilon

只会清理哨兵。

用四个词对语言进行可能的描述:

所有字符串的集合