左线性和右线性语法

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）。 我正在为Right Linear Grammar编写规则（留下练习为Left Linear Grammar编写类似的规则）

注意：大写字母用于变量，而小写用于语法中的终端。 NULL符号是^。术语“任何数字”表示*星形闭合的零次或多次。

[基本理念]

• 单一终端：如果RE只是e (e being any terminal)，我们可以编写G，只有一个生产规则S --> e（其中S is the start symbol），是一个等价的RG。
• UNION OPERATION：如果RE的形式为e + f，那么两个e and f are terminals，我们可以写G，有两个生产规则S --> e | f，是一个等价的RG。
• CONCATENATION：如果RE的形式为ef，那么两个e and f are terminals，我们可以用两个生产规则G写S --> eA, A --> f，是一个等价的RG。
• STAR CLOSURE：如果RE的形式为e*，其中e is a terminal和* Kleene star closure操作，我们可以在G中编写两个生产规则，S --> eS | ^，是等效的RG。
• PLUS CLOSURE：如果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。
• 加上UNION的关闭：如果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 | ^ 字符串可以从0s和1s的任何字符串开始，这就是为什么包含规则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的实例，则会有一个B，因为（A）* B和B是11。 一些示例字符串{^，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)*之类的模式结束。如果模式不为null，则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的种类形成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结构的相似性。在你不理解第一个之前不要前进

Answer 2

将正则表达式转换为左或右线性常规语法的规则