正则表达式

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

希望帮助你理解。

祝你好运！