我需要帮助构建以下语言的左线性和右线性文法？
a) (0+1)*00(0+1)*
b) 0*(1(0+1))*
c) (((01+10)*11)*00)*
对于 a) 我有以下内容:
Left-linear
S --> B00 | S11
B --> B0|B1|011
Right-linear
S --> 00B | 11S
B --> 0B|1B|0|1
这是正确的吗？我需要帮助解决B和C。
左线性和右线性语法
22
- user1585646
2个回答
99
从正则表达式构建等价的正则语法
首先，我会提供一些简单的规则来从正则表达式(RE)构建出正则语法(RG)，以下规则适用于右线性文法（对于左线性文法的类似规则留作练习）。
注意：在语法中，大写字母表示变量，小写字母表示终结符。空符号为^。词项'任意数量'表示零个或多个，即 * 星号闭包。
[基本思路]
单一终结符：如果RE是一个简单的表达式
e（e可以是任何终结符），那么我们可以编写只有一个产生式规则S --> e（其中S为起始符号）的RG，这是一个等价的RG。并集操作：如果RE为形式为
e + f的表达式，其中e和f均为终结符，则可以编写具有两个产生式规则S --> e | f的RG，这是一个等价的RG。连接操作：如果RE为形式为
ef的表达式，其中e和f均为终结符，则可以编写具有两个产生式规则S --> eA, A --> f的RG，这是一个等价的RG。星号闭包：如果RE为形式为
e*的表达式，其中e是终结符且*是克林星运算符，则可以在G中编写两个产生式规则S --> eS | ^，这是一个等价的RG。加号闭包：如果RE为形式为
e+的表达式，其中e是终结符且+是克林加运算符，则可以在G中编写两个产生式规则S --> eS | e，这是一个等价的RG。并集上的星号闭包：如果RE为形式为
(e + f)*的表达式，其中e和f均为终结符，则可以在G中编写三个产生式规则S --> eS | fS | ^，这是一个等价的RG。并闭包: 如果正则表达式为 (e + f)+，其中
e 和 f 都是终端符号，那么可以在G中编写四个产生式规则，S --> eS | fS | e | f，这是等效的 RG。星闭包: 如果正则表达式为 (ef)*，其中
e 和 f 都是终端符号，那么可以在G中编写三个产生式规则，S --> eA | ^, A --> fS，这是等效的 RG。加闭包: 如果正则表达式为 (ef)+，其中
e 和 f 都是终端符号，那么可以在G中编写三个产生式规则，S --> eA, A --> fS | f，这是等效的 RG。确保您理解以上所有规则，下面是总结表格：
+-------------------------------+--------------------+------------------------+ | TYPE | REGULAR-EXPRESSION | RIGHT-LINEAR-GRAMMAR | +-------------------------------+--------------------+------------------------+ | SINGLE TERMINAL | e | S --> e | | UNION OPERATION | e + f | S --> e | f | | CONCATENATION | ef | S --> eA, A --> f | | STAR CLOSURE | e* | S --> eS | ^ | | PLUS CLOSURE | e+ | S --> eS | e | | STAR CLOSURE ON UNION | (e + f)* | S --> eS | fS | ^ | | PLUS CLOSURE ON UNION | (e + f)+ | S --> eS | fS | e | f | | STAR CLOSURE ON CONCATENATION | (ef)* | S --> eA | ^, A --> fS | | PLUS CLOSURE ON CONCATENATION | (ef)+ | S --> eA, A --> fS | f | +-------------------------------+--------------------+------------------------+注意: 符号
e和f是终结符，^是空符号，S是开始变量[ANSWER]
现在，我们可以来看看你的问题。
a)
(0+1)*00(0+1)*语言描述: 所有字符串由0和1组成，至少包含一对
00。右线性文法:
S --> 0S | 1S | 00A
A --> 0A | 1A | ^字符串可以以任何由
0和1组成的字符串开头，因此包括规则S --> 0S | 1S。由于至少有一对00，所以没有空符号。S --> 00A被包括在内，因为00之后可以是0或1。符号A负责在00之后的0和1。左线性文法:
S --> S0 | S1 | A00
A --> A0 | A1 | ^
b)
0*(1(0+1))*语言描述: 任意数量的
0，后跟任意数量的10和11。
{因为1（0 + 1）= 10 + 11}右线性文法:
S --> 0S | A | ^
A --> 1B
B --> 0A | 1A | 0 | 1字符串以任意数量的
0开头，因此包括规则S --> 0S | ^，然后使用A --> 1B生成任意次数的10和11，并使用B --> 0A | 1A | 0 | 1。其他可行的右线性文法可以是
S --> 0S | A | ^
A --> 10A | 11A | 10 | 11左线性文法:
S --> A | ^
A --> A10 | A11 | B
B --> B0 | 0另一种形式可以是
S --> S10 | S11 | B | ^
B --> B0 | 0
c)
(((01+10)*11)*00)*语言描述：首先，该语言包含空字符串^，因为每个括号中的内容都被外部的*（星号）所包围。此外，如果字符串不为空，则一定以00结尾。可以将这个正则表达式简单地表示为（（（A）*B）*C）*，其中（A）*是（01+10）*，即01和10的任意重复次数。如果字符串中存在A，则一定存在B，因为（A）*B且B为11。
一些例子字符串：{^，00，0000，000000，1100，111100，1100111100，011100，101100，01110000，01101100，0101011010101100，101001110001101100 ... }左线性文法：
S --> A00 | ^
A --> B11 | S
B --> B01 | B10 | AS --> A00 | ^是因为任何字符串都是空或者如果它不是空，则以00结尾。当字符串以00结尾时，变量A匹配模式((01 + 10)* + 11)*。同样，此模式可以为空，或者必须以11结尾。如果它为空，则A会将其与S再次匹配，即字符串以类似于(00)*的模式结尾。如果该模式非空，则B与(01 + 10)*匹配。当B匹配所有可能时，A再次开始匹配字符串。这关闭了最外层的*。右线性文法：
S --> A | 00S | ^
A --> 01A | 10A | 11S
你问题的第二部分：
For a) I have the following: Left-linear S --> B00 | S11 B --> B0|B1|011 Right-linear S --> 00B | 11S B --> 0B|1B|0|1(答案)
以下是你的解决方案存在问题的原因：左线性文法是错误的，因为字符串
0010无法生成。 右线性文法也是错误的，因为字符串1000无法生成。尽管两者都在问题（a）的正则表达式生成的语言中。编辑
添加每个正则表达式的DFA，以便人们可以找到它有用。a)
(0+1)*00(0+1)*
b)
0*(1(0+1))*
c)
(((01+10)*11)*00)*为这个正则表达式绘制DFA是麻烦而复杂的。
为此我想添加DFA简化任务的方法是，我们应该思考RE的形成方式 对我来说，RE
(((01+10)*11)*00)*看起来像(a*b)*(((01+10)*11)* 00 )* ( a* b )*实际上，上述表达式中的
a本身就是以(a*b)*的形式表示的，即((01+10)*11)*RE
(a*b)*相当于(a + b)*b + ^。(ab)的DFA如下所示:
((01+10)*11)*的DFA为:
(((01+10)*11)* 00 )*的DFA为:
尝试寻找以上三个DFA的构造相似之处，只有在理解第一个之前不要继续向前移动
- Grijesh Chauhan
14
5
将正则表达式转换为左线性或右线性正则文法的规则
- lordvcs
1
从这里复制：https://cs.stackexchange.com/questions/68575/steps-to-convert-regular-expressions-directly-to-regular-grammars-and-vice-versa - Mahesha999
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
(0+1)的含义是如果出现了0，就必须同时出现1。" 不是，它的含义是可以出现0或者1，在形式语言中二元运算符+代表并集。 - Grijesh Chauhan