0

首先，我不知道这是否是我所要求的正确翻译。

在我的一门课程中，我们只是盯着学习正则表达式、形式语言等。

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 的示例/问题。我不明白这是怎么做到的。

4

3 回答 3

3

您所拥有的是一种常规语言，使用上下文无关语法定义。定义相同语言的正则表达式是(0)U(1{0,1}*). 在简单的英语中，常规语言包含所有以 1 开头的 0 和 1 字符串，以及字符串 0。

上下文无关文法以一些初始的非终结符号开头，在这种情况下它似乎是 S。然后您可以根据列出的产生式规则将任何非终结符号替换为一串符号。当字符串不包含非终结符时，它是“完成”。

在您的示例中，如果字符串中当前存在要替换的 S 或 R，则只能“选择 1R”。正如这种语法所发生的那样，第一次将 R 替换为 1 时，您不再需要替换任何非终结符，并且字符串的生成完成。

编辑：这是 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
于 2011-02-14T18:42:02.797 回答
2

你是对的。不允许追加，只能替换。但是，使用这种语言，您可以通过选择“R ::= 1R”或“R ::= 0R”来不断地延长字符串，然后再次替换 R。

于 2011-02-14T18:29:27.043 回答
1

如果我从 1R 开始，那么只有 1....那么句子（在这种情况下是二进制数）是完整的，对吗？

是的，这是正确的。句子 11 匹配 S = 1R = 11。

但是，使用这种语法，您始终可以使用 R = 1R 或 R= 0R 在句子中添加越来越多的数字。

编辑：针对问题编辑：

如何生成 1100110？

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

希望能帮助你理解。

祝你好运！

于 2011-02-14T18:31:03.403 回答