22

我需要帮助为以下语言构建左线性和右线性语法？

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

4

2 回答 2

94

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

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

注意：大写字母用于变量，小写用于语法中的终结符。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*, wheree is a terminal和* Kleene star closureoperation，我们可以写出两个产生式规则G, S --> eS | ^, 是一个等价的 RG。

  • PLUS CLOSURE：如果 RE 的形式是 e + , where e is a terminaland + Kleene plus closureoperation, 我们可以写出两个产生式规则G, S --> eS | e, 是一个等价的 RG。

  • UNION 上的 STAR CLOSURE： 如果 RE 的形式为 (e + f)*，其中两者e and f are terminals，我们可以在 中写三个产生式规则G，S --> eS | fS | ^，是等价的 RG。

  • PLUS CLOSURE ON UNION： 如果 RE 的形式是 (e + f) +，其中两者e and f are terminals，我们可以在 , 中写出四个产生式规则G，S --> eS | fS | e | f是等价的 RG。

  • STAR CLOSURE ON CONCATENATION： 如果 RE 是 (ef)* 的形式，其中两者e and f are terminals，我们可以在 , 中编写三个产生式规则G，S --> eA | ^, A --> fS是等价的 RG。

  • PLUS CLOSURE ON CONCATENATION： 如果 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 |
+-------------------------------+--------------------+------------------------+

注意：符号eandf是终结符，^ 是 NULL 符号，并且S是起始变量

[回答]

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

一个） (0+1)*00(0+1)*

语言描述：所有字符串由 0 和 1 组成，至少包含一对00.

  • 右线性语法：

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

    字符串可以以0s 和1s 的任何字符串开头，这就是包含规则的原因s --> 0S | 1S，并且因为至少有一对00，所以没有空符号。S --> 00A被包含是因为0，1可以在之后00。该符号A负责处理 . 之后的 0 和 1 00。

  • 左线性语法：

    S --> S0 | S1 | A00
    A --> A0 | A1 | ^

b) 0*(1(0+1))*

语言描述：任意数量的 0，后跟任意数量的 10 和 11。
{ 因为 1(0 + 1) = 10 + 11 }

  • 右线性语法：

    S --> 0S | 一个 | ^
    A --> 1B
    B --> 0A | 1A | 0 | 1

    字符串以任意数量的0so 规则开始S --> 0S | ^，然后包含用于生成10和11任意次数的规则A --> 1B and B --> 0A | 1A | 0 | 1。

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

    S --> 0S | 一个 | ^
    A --> 10A | 11A | 10 | 11

  • 左线性语法：

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

    另一种形式可以是

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

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

语言描述：首先是语言包含 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 | S
    B --> B01 | B10 | 一个

    S --> A00 | ^因为任何字符串要么为空，要么如果不为空，则以00. 当字符串以 结尾时00，变量A与模式匹配((01 + 10)* + 11)*。同样，此模式可以为 null 或必须以 . 结尾11。如果它为null，则再次A匹配它，S即字符串以模式结束(00)*。如果模式不为空，则B与 匹配(01 + 10)*。当B匹配所有它可以时，A再次开始匹配字符串。这将关闭最外面的 * in ((01 + 10)* + 11)*。

  • 右线性语法：

    S --> A | 00年代 | ^
    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。以便人们发现它很有帮助。

一个） (0+1)*00(0+1)*

DFA

b) 0*(1(0+1))*

DFA

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 + ^。(a b)的 DFA如下：

DFA

DFA 为((01+10)*11)*：

DFA

DFA 为(((01+10)*11)* 00 )*：

DFA

尝试在上述三个 DFA 的构造中找到相似之处。在你不理解第一个之前不要继续前进

于 2012-12-19T05:13:32.823 回答
5

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

于 2018-01-20T12:43:46.473 回答