左线性和右线性语法

本文介绍了左线性和右线性语法的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我需要为以下语言构造左线性和右线性语法吗?

I need help with constructing a left-linear and right-linear grammar for the languages below?

a)  (0+1)*00(0+1)*
b)  0*(1(0+1))*
c)  (((01+10)*11)*00)*

对于a)我有以下内容:

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

这是正确的吗?我需要b& amp;的帮助c.

Is this correct? I need help with b & c.

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

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

Constructing an equivalent Regular Grammar from a Regular Expression

First, I start with some simple rules to construct Regular Grammar(RG) from Regular Expression(RE).
I am writing rules for Right Linear Grammar (leaving as an exercise to write similar rules for Left Linear Grammar)

注意:大写字母用于表示变量，而小写则用于表示语法的末尾. NULL符号是^.术语任何数字" 表示零次或多次，即*星形关闭.

NOTE: Capital letters are used for variables, and small for terminals in grammar. NULL symbol is ^. Term 'any number' means zero or more times that is * star closure.

[ BASIC IDEA ]

单终端:如果RE仅是e (e being any terminal)，我们可以写G，而只有一个生产规则S --> e(其中S is the start symbol)是等效的. RG.

SINGLE TERMINAL: If the RE is simply e (e being any terminal), we can write G, with only one production rule S --> e (where S is the start symbol), is an equivalent RG.

联盟操作::如果RE的形式为e + f，其中两个e and f are terminals，我们都可以写成G，其中有两个生产规则S --> e | f，等效RG.

UNION OPERATION: If the RE is of the form e + f, where both e and f are terminals, we can write G, with two production rules S --> e | f, is an equivalent RG.

CONCATENATION::如果RE的格式为ef，则我们都可以用两个生产规则S --> eA, A --> f来写G，我们可以写G RG.

CONCATENATION: If the RE is of the form ef, where both e and f are terminals, we can write G, with two production rules S --> eA, A --> f, is an equivalent RG.

星级关闭:如果RE的格式为e*，其中e is a terminal和* Kleene star closure操作，我们可以在G，是等效的RG.

STAR CLOSURE: If the RE is of the form e*, where e is a terminal and * Kleene star closure operation, we can write two production rules in G, S --> eS | ^, is an equivalent RG.

加结束语::如果RE的形式为e ，其中e is a terminal和+ Kleene plus closure操作，我们可以在其中编写两个生产规则G，S --> eS | e是等效的RG.

PLUS CLOSURE: If the RE is of the form e, where e is a terminal and + Kleene plus closure operation, we can write two production rules in G, S --> eS | e, is an equivalent RG.

联盟上的星级关闭::如果RE的形式为(e + f)*，其中两个均为e and f are terminals，我们可以在G，S --> eS | fS | ^是等效的RG.

STAR CLOSURE ON UNION: If the RE is of the form (e + f)*, where both e and f are terminals, we can write three production rules in G, S --> eS | fS | ^, is an equivalent RG.

在同盟上加盖封闭:如果RE的格式为(e + f)，其中两个e and f are terminals都可以写成四个G，S --> eS | fS | e | f中的规则是等效的RG.

PLUS CLOSURE ON UNION: If the RE is of the form (e + f), where both e and f are terminals, we can write four production rules in G, S --> eS | fS | e | f, is an equivalent RG.

明星赛的封闭时间::如果RE的格式为(ef)*，其中两个e and f are terminals，我们都可以在G，S --> eA | ^, A --> fS中编写三个生产规则是等效的RG.

STAR CLOSURE ON CONCATENATION: If the RE is of the form (ef)*, where both e and f are terminals, we can write three production rules in G, S --> eA | ^, A --> fS, is an equivalent RG.

加上连接的关闭提示:如果RE的格式为(ef)，其中两个e and f are terminals，我们都可以在其中编写三个生产规则G，S --> eA, A --> fS | f是等效的RG.

PLUS CLOSURE ON CONCATENATION: If the RE is of the form (ef), where both e and f are terminals, we can write three production rules in G, S --> eA, A --> fS | f, is an equivalent RG.

请确保您了解上述所有规则，这是摘要表:

Be sure that you understands all above rules, here is the summary table:

+-------------------------------+--------------------+------------------------+
| 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 |
+-------------------------------+--------------------+------------------------+

[ANSWER]

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

Now, we can come to you problem.

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

右线性语法:
- Right Linear Grammar:
  S-> 0S | 1S | 00A
  A-> 0A | 1A | ^
  S --> 0S | 1S | 00A
  A --> 0A | 1A | ^
  字符串可以以任何0和1字符串开头，这就是为什么要包含规则s --> 0S | 1S的原因，并且因为至少有一对00，所以没有空符号.之所以包含S --> 00A是因为0，1可以在00之后.符号A表示00之后的0和1.
  String can start with any string of 0s and 1s thats why included rules s --> 0S | 1S and Because at-least one pair of 00 ,there is no null symbol. S --> 00A is included because 0, 1 can be after 00. The symbol A takes care of the 0's and 1's after the 00.
  左线性语法:
  S-> S0 | S1 | A00
  A-> A0 | A1 | ^
  S --> S0 | S1 | A00
  A --> A0 | A1 | ^
  b) 0*(1(0+1))*
  - 右线性语法:
    - Right Linear Grammar:
      S-> 0S | A | ^
      A-> 1B
      B-> 0A | 1A | 0 | 1
      S --> 0S | A | ^
      A --> 1B
      B --> 0A | 1A | 0 | 1
      字符串以任意数量的0开头，因此包含规则S --> 0S | ^，然后为使用A --> 1B and B --> 0A | 1A | 0 | 1生成任意次数的10和11的规则.
      String starts with any number of 0 so rule S --> 0S | ^ are included, then rule for generating 10 and 11 for any number of times using A --> 1B and B --> 0A | 1A | 0 | 1.
      其他可选的右线性语法可以是
      Other alternative right linear grammar can be
      S-> 0S | A | ^
      A-> 10A | 11A | 10 | 11
      S --> 0S | A | ^
      A --> 10A | 11A | 10 | 11
      左线性语法:
      S-> A | ^
      A-> A10 | A11 | B
      B-> B0 | 0
      S --> A | ^
      A --> A10 | A11 | B
      B --> B0 | 0
      另一种形式可以是
      S-> S10 | S11 | B | ^
      B-> B0 | 0
      S --> S10 | S11 | B | ^
      B --> B0 | 0
      c) (((01+10)*11)*00)*
      - 左线性语法:
        Left Linear Grammar:
        S-> A00 | ^
        A-> B11 | S
        B-> B01 | B10 |
        S --> A00 | ^
        A --> B11 | S
        B --> B01 | B10 | A
        S --> A00 | ^，因为任何字符串都不为null，或者如果不为null，则以00结尾.当字符串以00结尾时，变量A匹配模式((01 + 10)* + 11)*.同样，此模式可以为null或必须以11结尾.如果其为空，则A再次将其与S匹配，即字符串以类似(00)*的模式结尾.如果模式不为空，则B与(01 + 10)*匹配.当B完全匹配时，A再次开始匹配字符串.这将关闭((01 + 10)* + 11)*中最外面的*.
        S --> A00 | ^ because any string is either null, or if it's not null it ends with a 00. When the string ends with 00, the variable A matches the pattern ((01 + 10)* + 11)*. Again this pattern can either be null or must end with 11. If its null, then A matches it with S again i.e the string ends with pattern like (00)*. If the pattern is not null, B matches with (01 + 10)*. When B matches all it can, A starts matching the string again. This closes the out-most * in ((01 + 10)* + 11)*.
        右线性语法:
        S-> A | 00S | ^
        A-> 01A | 10A | 11S
        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
        ( answer )
        出于以下原因，您的解决方案是错误的，
        (answer)
        You solution are wrong for following reasons,
        左线性语法错误，因为无法生成字符串0010.右线性语法是错误的，因为不可能生成字符串1000.尽管两者都是由问题(a)的正则表达式生成的语言.
        Left-linear grammar is wrong Because string 0010 not possible to generate.Right-linear grammar is wrong Because string 1000 is not possible to generate. Although both are in language generated by regular expression of question (a).
        编辑
        为每个正则表达式添加DFA.以便对您有所帮助.
        EDIT
        Adding DFA's for each regular expression. so that one can find it helpful.
        a) (0+1)*00(0+1)*
        b) 0*(1(0+1))*
        c) (((01+10)*11)*00)*
        为此正则表达式绘制DFA既复杂又复杂.
        
        Drawing DFA for this regular expression is trick and complex.
        
        为简化任务，我们应该考虑稀土的种类形成对我来说，RE (((01+10)*11)*00)*看起来像(a*b)*
        To simplify the task, we should think the kind formation of REto me the RE (((01+10)*11)*00)* looks like (a*b)*
        (((01+10)*11)* 00 )* ( a* b )*
        实际上在上面的表达式a中，它以(a*b)*的形式出现那是((01+10)*11)*
        Actually in above expression a it self in the form of (a*b)*that is ((01+10)*11)*
        RE (a*b)*等于(a + b)*b + ^. (a b)的DFA如下:
        RE (a*b)* is equals to (a + b)*b + ^. The DFA for (ab) is as belows:
        ((01+10)*11)*的DFA是:
        (((01+10)*11)* 00 )*的DFA是:
        
        这篇关于左线性和右线性语法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！
        
        1403页，肝出来的..