左线性和右线性语法

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操作:如果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关闭:如果RE是形式的e*,在那里e is a terminal和* Kleene star closure操作,我们可以写两个生产规则G,S --> eS | ^是一个相当于RG.

• PLUS闭幕:如果RE的形式电子商务⁺,其中e is a terminal和+ Kleene plus closure操作,我们可以写两个生产规则G,S --> eS | e是一个相当于RG.

• STAR CLOSURE ON UNION: 如果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 ON闭幕串联: 如果RE的形式(EF)*,其中两个的e and f are terminals,我们可以写三个生产规则G,S --> eA | ^, A --> fS是一个相当于RG.

• PLUS CLOSURE ON级联: 如果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是起始变量

[回答]

现在,我们可以找到你的问题.

一个) (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处理后的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 | ^
  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
  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,101000010001101100 ....}

• 左线性语法:

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

  S --> A00 | ^因为任何字符串都是null,或者如果它不是null,则以a结尾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.这样人们就会发现它很有帮助.

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

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

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

为这个正则表达式绘制DFA既诡计又复杂.
_{为此,我想添加DFA}

为了简化任务,我们应该认为RE的(((01+10)*11)*00)* 样子形成RE(a*b)*

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

实际上在上述表达式a中的形式,它自(a*b)* 认为是((01+10)*11)*

RE (a*b)*等于(a + b)*b + ^.(a b)的DFA 如下:

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

DFA (((01+10)*11)* 00 )*是:

_{试着找出上述三种DFA结构的相似性.在你不理解第一个之前不要前进}

Answer 2

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