Как вы делаете последний шаг при конвертации CFG в CNF?

Question

Дано:

    S->AcA|BcB
    A->ccBc|ABA|cc
    B->c

step1

    S0->S
    S->AcA|BcB
    A->ccBc|ABA|cc
    B->c


step2             // change symbol to terminals?

    S0->S
    S->ABA|BBB
    A->BBBB|ABA|BB
    B->c

step3             // split?

    S0->S
    S->ABA
    S->BBB
    A->BBBB
    A->ABA
    A->BB
    B->c

step4             // what to do when A->AXA?

    S0->S
    S->ABA
    S->BBB
    A->BBBB   //??
    A->ABA    //??
    A->BB     //??
    B->c

Я не уверен, как продолжить.

Answer 1

Там нет шага 2 для вас. Шаг 2 - удаление правил epsilon, а у вас нет правил epsilon.

У вас также нет шага 3, потому что B->c имеет терминал - не нетерминал - в правой части. Нет единичных правил вида:

Terminal -> Terminal.

Это оставляет нас после вашего шага 1:

S0 -> S
S -> AcA|BcB
A -> ccBc|ABA|cc
B -> c

Вам необходимо получить остальные ваши правила в виде:

X -> YZ //where X,Y,Z are all nonterminals

Чтобы преобразовать строку нетерминалов и терминалов в вышеприведенную форму, вы берете первый нетерминал или терминал с фронта, а затем превращаете оставшуюся часть строки в новое правило и используете это правило в конце. Я не очень хорошо это объяснил, поэтому давайте рассмотрим пример.

//To convert
S -> AcA
//we split it into A and cA, and define a new rule C -> cA, giving:
S -> AC
C -> cA
//Then, C -> cA needs to be converted to the same form, so just replace c with B
S -> AC
C -> BA

Тем не менее, выбросить выше, потому что сначала я собираюсь просто изменить все cс B, так как это произойдет в любом случае:

S0 -> S
S -> ABA|BBB
A -> BBBB|ABA|BB
B -> c

Теперь, когда я снова посмотрю на ваш вопрос, это то, где вы были. Вы сделали еще один шаг вперед, чтобы:

S0 -> S
S -> ABA
S -> BBB
A -> BBBB
A -> ABA
A -> BB
B -> c

Если мы возьмем первый S и используем метод, описанный выше, мы получим:

S -> ABA
//goes to
S -> AC
C -> BA

Выполняя остальные правила, получаем:

//second S
S -> BD
D -> BB

//first A
A -> DD

//second A:
A -> AC

Комбинируя все это, мы получаем:

S0 -> S
S -> AC
S -> BD
A -> DD
A -> AC
A -> BB
B -> c
C -> BA
D -> BB