正則表達式

Question

首先，我不知道這是否是我所問的正確翻譯。

在我的一門課程中，我們只是盯着學習正則表達式，正式語言等等。

Alphabet {1,0,S,R} 
Terminals {1,0} 
Rules: 

S ::= 0 
S ::= 1 
S ::= 1R 
R ::= 1R 
R ::= 0R 
R ::= 1 
R ::= 0 

在這種情況下，假設我從1R開始，那麼我可以繼續使用1R或0R。

如果我從1R開始，那麼只是一個1 ....那麼句子（在這種情況下，它的二進制數）是完整的嗎？因爲後來我不能「追加」一些東西，比如說1R然後我選擇1然後我再選擇1R？

在此先感謝，如果它不正確，請重新標記/移動帖子。

---

新增：

0 at rule S ::= 0 
1 with S ::= 1 
10 with S ::= 1R, so R ::= 0 

如何生成1100110？

這不是家庭作業，它是來自powerpoint的示例/問題。我不明白這是如何完成的。

Answer 1

你在那裏有一種常規語言，使用上下文無關語法定義。定義相同語言的正則表達式是(0)U(1{0,1}*)。用普通英語，常規語言包含以1開頭的所有0和1字符串，以及字符串0.

上下文無關語法以一些初始非終端符號開始，在這種情況下它看起來是S.然後，您可以根據列出的生產規則，用一串符號替換任何非終端符號。當字符串不包含非終端符號時，它是「完成」的。

在您的示例中，如果要替換的字符串中有S或R，則只能選擇「1R」。正如這個語法所發生的那樣，當你第一次用R代替R時，你不再有任何非終端來替換，並且字符串的產生已經完成。

編輯：這是生產1100110.

S 
1R   via S ::= 1R 
11R  via R ::= 1R 
110R  via R ::= 0R 
1100R  via R ::= 0R 
11001R  via R ::= 1R 
110011R via R ::= 1R 
1100110 via R ::= 0 

Answer 2

你是對的。追加是不允許的，只有替代。然而，使用這種語言，您可以通過選擇「R :: = 1R」或「R :: = 0R」來持續增加字符串的長度，然後再次替換R。

Answer 3

如果我從1R開始，那麼只是一個1 ....那麼句子（在這種情況下，它的二進制數）是完整的嗎？

是的，這是正確的。句子11匹配S = 1R = 11。

然而，對於這種語法，您總是可以使用R = 1R或R = 0R爲句子添加更多的數字。

編輯：在回答這個問題編輯：

如何生成1100110？

1100110 = S = 1R = 11R = 110R = 1100R = 11001R = 110011R = 1100110

希望幫助你理解。

祝你好運！