無限制語法

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 s到0秒。實際上，單個X遞增二進制數字而不改變其字符串長度（或卡住）。

前導Y將重寫所有1 s到所有0 s（或卡住）的字符串。

將L的規則視爲字符串右側部分的可能操作。 L => L0Y會將字符串從全1重置爲全零，並將其長度增加1。 L => LX將增加任何其他號碼，但如果值最大則失敗。

這兩個操作一起足以生成（低效）所有零和一個字符串（包括空字符串）。

L -> epsilon 
R -> epsilon 

只會清理哨兵。

內四個字語言的一個可能的描述：

集中的所有字符串