Изменения
Опечатка в правилах вывода из S в шагах 4 и 5
:<tex> S \rightarrow \varepsilon </tex>
где <tex> a </tex> {{---}} терминал, <tex> A </tex> {{---}} нетерминал(возможно, стартовый), <tex> S </tex> {{---}} стартовый нетерминал (причём он не должен встречаться в правых частях правил), <tex> \varepsilon </tex> {{---}} пустая строка, <tex> \gamma </tex> {{---}} строка из не более, чем двух нетерминалов. Таким образом, пустая строка выводится только из стартового нетерминала, однако он по-прежнему может участвовать в формировании правил первого типа. (Это утверждение применимо и к ослабленной нормальной форме Грейбах)
}}
:<tex> S \rightarrow \varepsilon </tex>
где <tex> a </tex> {{---}} терминал, <tex> A </tex> {{---}} нетерминал(возможно, стартовый), <tex> S </tex> {{---}} стартовый нетерминал (причём он не должен встречаться в правых частях правил), <tex> \varepsilon </tex> {{---}} пустая строка, <tex> \gamma </tex> {{---}} строка из произвольного числа терминалов и нетерминалов.
}}
#* <tex> A_i \rightarrow A_j \gamma </tex>, где <tex> A_i </tex>, <tex> A_j </tex> {{---}} нетерминалы, <tex> a </tex> {{---}} терминал, <tex> \gamma </tex> {{---}} произвольная последовательность из терминалов и нетерминалов, <tex> i < j </tex>.
#Воспользуемся следующей функцией для придания грамматике нужного вида:
'''greibahfunction'''greibah(правила <tex>A_1 \dots A_n</tex> из контекстно-свободной грамматики <tex> \Gamma </tex>) :
'''for''' i = n .. 1
'''for''' j = i + 1 .. n
Для каждого правила вывода из <tex> A_j </tex> вида <tex> A_j \rightarrow \delta_1 | \ldots | \delta_k </tex> заменить каждое правило <tex> A_i \rightarrow A_j \gamma </tex> на <tex> A_i \rightarrow \delta_1\gamma | \ldots | \delta_k\gamma </tex>.
После каждой итерации главного цикла все правила для <tex> A_k </tex> (где <tex>k \geqslant i</tex>) будут иметь вид <tex> A_k \rightarrow a \gamma </tex>.
|-
|''4. Выполняем функцию '''greibah''' для правила <tex>S\rightarrow XA|BB</tex>
|<tex>S\rightarrow bA|bABB|bB|bABZB|BZBbZB</tex> <br> <tex>B\rightarrow bAB|b|bABZ|bZ</tex> <br> <tex>Z\rightarrow BB|BBZ</tex> <br> <tex>X\rightarrow b</tex> <br> <tex>A\rightarrow a</tex>
|-
|''5. Выполняем функцию '''greibah''' для правила <tex>Z\rightarrow BB|BBZ</tex>
|<tex>S\rightarrow bA|bABB|bB|bABZB|BZBbZB</tex> <br> <tex>B\rightarrow bAB|b|bABZ|bZ</tex> <br> <tex>Z\rightarrow bABB|bB|bABZB|bZB|bABBZ|bBZ|bABZBZ|bZBZ</tex> <br> <tex>X\rightarrow b</tex> <br> <tex>A\rightarrow a</tex>
|}
<div style="clear:both;"></div>
