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

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

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

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

источник

2015-03-13 qqq

Я ж что похоже на надзор в форматировании кода. Я также исправил ошибочный тег; 'cnf' означает что-то отличное от нормальной формы Хомского здесь, как вы можете сказать из выдержки, показанной на паре над тегом или при вводе текста. Наконец, я переписал заголовок, чтобы быть хотя бы немного яснее, но он все еще нуждается чтобы быть более конкретным. Какая часть в том, что вам трудно понять? –

@NathanTuggy Он говорит в комментариях кода «Что вы делаете, когда A -> AXA?». Мне было ясно, что ему нужно, когда я обновил свои знания о CNF. –

@MillieSmith: Я знаю, что знание CNF ограничено именем и неопределенной идеей о том, что существуют формальные характеристики грамматики, поэтому я сделал все, что мог. Если вы снова можете переписать заголовок, чтобы сделать его конкретным, это было бы очень полезно для будущей справки. –

Для вас нет второго шага. Step 2 is removing epsilon rules, и у вас нет правил 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

источник

2015-03-13 22:54:31

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

ответ

Смежные вопросы