Преобразование контекстно-свободной грамматики в обычную грамматику - PullRequest
Новая
       71

Преобразование контекстно-свободной грамматики в обычную грамматику

2 голосов
/ 30 апреля 2020

Интересно, как спроектировать эту обычную грамматику или как преобразовать мою контекстно-свободную грамматику в обычную грамматику (например, A-> aA). Я пытался, но безрезультатно.

Вопрос: Набор строки на Σ = {a, b}, которые содержат как минимум два вхождения aaa и как минимум одно вхождение bbbb. [aaaabbbb count]. Грамматика должна быть регулярной.

Мой ответ на CFG: «А» проверит, встречается ли «aaaa» в слове, или нет Б, проверит, встречается ли в слове «bbb» или нет C проверит, ааа 'встречаются в слове как минимум дважды или нет

S -> AB | BA | CB C | CCB | B CC

A -> aaaa | аА | Аа | Ба | Ab

B -> bbb | АБ | Ба | бб | Bb

C -> ааа | C | Ca | б C | Cb

1 Ответ

2 голосов
/ 01 мая 2020

Чтобы получить обычную грамматику, вы можете сначала попытаться записать DFA; преобразование DFA в правильную грамматику тривиально. Чтобы получить DFA, мы можем использовать конструкцию Cartesian Product Machine здесь.

Начнем с DFA для языков L1, содержащих aaaa или двух экземпляров aaa, и L2, содержащих bbbb. 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

Декартовая конструкция машины даст нам DFA из 35 состояний: восемь состояний в первом и пять состояний во втором. Мы будем называть эти состояния 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.

...