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 s。实际上，单个 X增加二进制数而不改变其字符串长度(或卡住)。

领先 Y将重写所有 1 的字符串对所有人 0 s(或卡住)。

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

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

L  -> epsilon 
R  -> epsilon

只会清理哨兵。

用四个词对语言的一种可能描述:

所有字符串的集合