grammar - 左线性和右线性语法

Question

在为以下语言构造左线性和右线性语法时，我需要帮助吗？

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的帮助。

Answer 1

从正则表达式构造等效的正则语法

首先，我从一些简单的规则开始，从正则表达式（RE）构造正则语法（RG）。
我正在为“右线性语法”编写规则（作为练习，为“左线性语法”编写类似规则）

注意：大写字母用于变量，小号用于语法末尾。 NULL符号是^。术语“任何数字”表示零次或多次，即*星形关闭。

[基本想法]


单终端：如果RE仅是e (e being any terminal)，我们可以写G，而只有一个生产规则S --> e（其中S is the start symbol）是等效的RG。
联合操作：如果RE的格式为e + f，则两个e and f are terminals都可以写成G，其中两个生产规则S --> e | f是等效的RG。
结论：如果RE的格式为ef，则两个e and f are terminals都可以写成G，其中两个生产规则S --> eA, A --> f是等效的RG。
结束语：如果RE的格式为e*，其中e is a terminal和* Kleene star closure运算，我们可以在G中编写两个生产规则，S --> eS | ^是等效的RG。
加句号：如果RE的形式为e +，其中e is a terminal和+ Kleene plus closure操作，我们可以在G中编写两个生产规则，S --> eS | e是等效的RG。
联盟上的星级关闭：如果RE的形式为（e + f）*，其中两个e and f are terminals，我们都可以在G中编写三个生产规则，S --> eS | fS | ^是等效的RG。
加上对联合的闭包：如果RE的形式为（e + f）+，其中两个e and f are terminals，我们可以在G中编写四个生产规则，S --> eS | fS | e | f是等效的RG。
星级关闭：如果RE的形式为（ef）*，其中两个e and f are terminals，我们都可以在G中写出三个生产规则，S --> eA | ^, A --> fS是等效的RG。
加上封闭状态：如果RE的形式为（ef）+，其中两个e and f are terminals，我们都可以在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是终端，^是NULL符号，而 S是起始变量


[回答]

现在，我们可以为您解决问题。

a） (0+1)*00(0+1)*


语言说明：所有字符串均由0和1组成，其中至少包含一对 00。



右线性语法：

S-> 0S | 1S | 00A
A-> 0A | 1A | ^

字符串可以以 0和 1的任何字符串开头，这就是为什么要包含规则 s --> 0S | 1S的原因，并且因为至少有一对 00，所以没有空符号。之所以包含 S --> 00A，是因为 0， 1可以在 00之后。符号 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 | ^，然后使用 10任意次数生成 11和 A --> 1B and B --> 0A | 1A | 0 | 1的规则。

其他可替代的右线性语法可以是

S-> 0S | A | ^
A-> 10A | 11A | 10 | 11
左线性语法：

S-> A | ^
A-> A10 | A11 |乙
B-> B0 | 0

另一种形式可以是

S-> S10 | S11 | B | ^
B-> B0 | 0


c） (((01+10)*11)*00)*


语言说明：首先是语言包含null（^）字符串，因为（）内的所有事物的外部都有一个*（星号）。同样，如果语言中的字符串不为null且以00结尾。那么，您可以简单地认为（（（A）* B）* C）*形式的正则表达式，其中（A）*为（01 + 10） *是01和10的任意重复数。
如果字符串中有一个A的实例，那么因为（A）* B和B为11，所以B肯定会成为B。
一些示例字符串{^，00，0000，000000，1100，111100，1100111100，011100，101100，01110000，01101100，0101011010101100，101001110001101100 ....}



左线性语法：

S-> A00 | ^
A-> B11 |小号
B-> B01 | B10 |一个

S --> A00 | ^，因为任何字符串都不为null，或者如果不为null，则以 00结尾。当字符串以 00结尾时，变量 A与模式 ((01 + 10)* + 11)*匹配。同样，此模式可以为null或必须以 11结尾。如果其为null，则 A再次将其与 S匹配，即字符串以类似 (00)*的模式结尾。如果模式不为空，则 B与 (01 + 10)*匹配。当 B完全匹配时， A再次开始匹配字符串。这将关闭 ((01 + 10)* + 11)*中最外面的*。
右线性语法：

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 (((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的构造中找到相似之处。在你不了解第一个之前不要前进