左线性和右线性语法

我需要帮助为下面的语言构build左线性和右线性语法？

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

用正则expression式构造一个等价的规则语法

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

注：大写字母用于variables，小写字母表示语法。 NULL符号是^ 。 术语“任何数字”意味着零星或更多次，即星号closures。

[ 基本思想 ]

• 单一terminal：如果RE仅仅是e (e being any terminal) ，那么我们可以写成G ，只有一个生产规则S --> e （其中S is the start symbol ）是等效的RG。

• 如果RE的forms是e + f ， e and f are terminals ，我们可以写成G ，有两条生产规则S --> e | f S --> e | f是等效的RG。

• 结合：如果RE的forms为ef ，那么e and f are terminals ，我们可以写成G ，有两个生产规则S --> eA, A --> f是等价的RG。

• STAR CLOSURE：如果RE的forms为e* ，其中e is a terminal和* Kleene star closure操作，我们可以在G ， S --> eS | ^ S --> eS | ^ ，是等效的RG。

• encryptionclosures：如果RE的forms是e ⁺ ，其中e is a terminal ， + Kleene plus closure操作，我们可以写出两个生产规则： G ， S --> eS | e S --> eS | e ，是一个等效的RG。

• 联盟的星际closures：如果RE的forms是（e + f）*，那么e and f are terminals ，我们可以写出三个生产规则： G ， S --> eS | fS | ^ S --> eS | fS | ^ S --> eS | fS | ^ ，是等效的RG。

• 如果RE的forms是（e + f） ⁺ ，那么e and f are terminals ，我们可以写出四个生产规则： G ， S --> eS | fS | e | f S --> eS | fS | e | f S --> eS | fS | e | f是等效的RG。

• 星形闭合：如果RE的forms是（ef）*， e and f are terminals ，我们可以写出G ， S --> eA | ^, A --> fS S --> eA | ^, A --> fS是等效的RG。

• 增加closures：如果RE的forms是（ef） ⁺ ，那么e and f are terminals ，我们可以写出三个生产规则： G ， S --> eA, A --> fS | f 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是terminal，^是NULL符号， S是起始variables

[回答]

现在，我们可以来找你的问题。

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

语言描述：所有string由0和1组成，至less包含一对00 。

• 正确的线性语法：

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

  string可以以0和1的任何string开始，这就是为什么包括规则s --> 0S | 1S s --> 0S | 1S和因为至less有一对00 ，没有零符号。 包含S --> 00A ，因为0可以在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

  string以任意数字0开始，因此规则S --> 0S | ^ S --> 0S | ^被包括在内，则使用A --> 1B and B --> 0A | 1A | 0 | 1规则生成10和11的次数 A --> 1B and B --> 0A | 1A | 0 | 1 A --> 1B and B --> 0A | 1A | 0 | 1 。

  其他可选的正确的线性语法可以

  S – > 0S | A | ^
  A – > 10A | 11A | 10 | 11

• 左线性语法：

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

  另一种forms可以是

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

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

语言描述：首先是语言包含null（^）string，因为在每个存在于（）内的事物之外有一个*（星号）。 （（A）* B）* C）*forms的正则expression式，其中（A）*是（01 + 10） *这是01和10的任何重复次数。如果在string中有一个A的实例，则会有一个B，因为（A）* B和B是11。
一些示例string{^，00,00000,000000,1100,111100,1100111100,011100,101100,01110000,01101100,01010110101100,101001110001101100 ….}

• 左线性语法：

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

  S --> A00 | ^ S --> A00 | ^因为任何string是null，或者如果它不是null，它以00结尾。 当string以00结尾时，variablesA匹配模式((01 + 10)* + 11)* 。 同样，这个模式可以是null或者以11结尾。 如果它为null，则A再次与S匹配，即string以(00)* 。 如果模式不为空，则B与(01 + 10)*匹配。 当B匹配时， A再次开始匹配string。 这将closures((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 

（ 回答 ）
你的解决办法是错误的，

左线性语法错误因为string0010不可能生成。 右线性语法错误因为string1000不可能生成。 虽然两者都是用正则expression式（a）产生的语言。

编辑
为每个正则expression式添加DFA。 所以人们可以发现它有帮助。

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

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

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

为这个正则expression式绘制DFA是诡计和复杂的。
_{为此，我想添加DFA}

为了简化任务，我们应该考虑对RE的(((01+10)*11)*00)*看起来像(a*b)*

 (((01+10)*11)* 00 )* ( a* b )* 

实际上，在(a*b)*forms中， ((01+10)*11)*

RE (a*b)*等于(a + b)*b + ^ 。 （ a）的DFA如下：

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

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

_{尝试find以上三种DFA的build设相似之处。 不要前进，直到你不明白第一个}