context-free-grammar - 将上下文无关文法转换为常规文法

Question

我想知道如何设计这种正则文法，或者如何将我的上下文无关文法转换为正则文法(如 A->aA)。我试过了，但没有结果。

问题:Σ ={a,b} 上的字符串集至少包含两次 aaa 和至少一次 bbbb.[aaaabbbb 计数]。语法要有规律。

我在CFG中的答案是A 将检查 'aaaa' 是否出现在单词中B 将检查 'bbb' 是否出现在单词中C 将检查 'aaa' 是否在单词中至少出现两次

S -> AB |学士 |加拿大广播公司 | build 银行 |密件抄送

A -> aaaa |一个|啊| BA |抗体

B -> bbb | AB |霸 | bB | Bb

C -> aaa | AC |钙 | BC | Cb

Answer 1

要想得到正则语法，可以先尝试写下一个DFA；将 DFA 转换为常规语法很简单。要获得 DFA，我们可以在此处使用笛卡尔积机构造。

从包含 aaaa 或 aaa 的两个实例的语言 L1 和包含 bbbb 的 L2 的 DFA 开始。这些的 DFA 很简单:

        b                          a,b
  /--+------+-------\             /--\
  \  |      |       |             \  |
   \ V      |       |              \ V
L1: q0--a-->q1--a-->q2--a-->q3--a-->q4
                           / ^
    /-+-----+---b---+----/   |
    | |     |                |
    V /     |                |
    q5--a-->q6--------a------/


                a                  a,b
  /--+------+-------+-------\     /--\
  \  |      |       |       |     \  |
   \ V      |       |       |      \ V
L2: q0--b-->q1--b-->q2--b-->q3--b-->q4

Cartesian Product Machine 构造将为我们提供一个 35 状态的 DFA:第一个状态为 8 个状态，第二个状态为 5 个状态。我们将这些状态称为 q00、q01、...、q64。那么常规语法只是编写转换的一种不同方式。这是它最终的样子:

q00 -> aq10 | bq01
q01 -> aq10 | bq02
q02 -> aq10 | bq03
q03 -> aq10 | bq04
q04 -> aq14 | bq04
q10 -> aq20 | bq01
q11 -> aq20 | bq02
q12 -> aq20 | bq03
q13 -> aq20 | bq04
q14 -> aq24 | bq04
q20 -> aq30 | bq01
q21 -> aq30 | bq02
q22 -> aq30 | bq03
q23 -> aq30 | bq04
q24 -> aq34 | bq04
q30 -> aq40 | bq51
q31 -> aq40 | bq52
q32 -> aq40 | bq53
q33 -> aq40 | bq54
q34 -> aq44 | bq54
q40 -> aq40 | bq41
q41 -> aq40 | bq42
q42 -> aq40 | bq43
q43 -> aq40 | bq44
q44 -> aq44 | bq44
q50 -> aq60 | bq51
q51 -> aq60 | bq52
q52 -> aq60 | bq53
q53 -> aq60 | bq54
q54 -> aq64 | bq54
q60 -> aq30 | bq51
q61 -> aq30 | bq52
q62 -> aq30 | bq53
q63 -> aq30 | bq54
q64 -> aq34 | bq54

我们注意到一些非终结符从未出现在产生式的右侧。我们可以通过去掉这些来简化语法:

q00 -> aq10 | bq01
q01 -> aq10 | bq02
q02 -> aq10 | bq03
q03 -> aq10 | bq04
q04 -> aq14 | bq04
q10 -> aq20 | bq01
q14 -> aq24 | bq04
q20 -> aq30 | bq01
q24 -> aq34 | bq04
q30 -> aq40 | bq51
q34 -> aq44 | bq54
q40 -> aq40 | bq41
q41 -> aq40 | bq42
q42 -> aq40 | bq43
q43 -> aq40 | bq44
q44 -> aq44 | bq44
q50 -> aq60 | bq51
q51 -> aq60 | bq52
q52 -> aq60 | bq53
q53 -> aq60 | bq54
q54 -> aq64 | bq54
q60 -> aq30 | bq51
q64 -> aq34 | bq54

这应该会让您非常接近您想要去的地方。此时我们只需要添加一些产生式来编码 q44 是唯一接受状态的事实。您可以添加 q44 -> e如果允许的话，或者只要你有q -> sq44添加额外的形式 q -> s .