Перевод правильной рекурсивной грамматики в нормальную форму Хомского

Question

Я пытаюсь выполнить упражнение, где я перевожу грамматику в нормальную форму Хомского. Я понимаю, как это сделать в обычных обстоятельствах, но на этот раз грамматика, с которой я работаю, рекурсивная. (Технически грамматика является ответом на предыдущий вопрос, поэтому я могу просто ошибиться гаммой.)

Я думаю, что могу сделать это, используя фиксированную последовательность правил вместо правил ε, но я хочу убедиться, что я не иду в неправильном направлении. Это проще объяснить на примере:

Для грамматики, которая выдает n 'a, где n больше 0 и кратно трем: (не волнуйтесь, это полностью отличается от грамматики моего реального упражнения)

S-> Aaaa
A-> Aaaa
A-> ε

Будет ли правильный перевод:

S0-> S
S-> A'B
A'-> AA'
A-> A'B
B-> B'C
A'-> a
B'-> a
C-> a

Answer 1

Хотя ваша грамматика является праворекурсивной, вы можете выполнить преобразование нормальной формы Хомского, как и любую другую (не правильную рекурсивную) грамматику.Просто следуйте алгоритму, изложенному в вашей книге, который, вероятно, состоит из двух шагов: (1) замените все вхождения терминалов a на правила A -> a , где A не встречается в наборе правил;(2) преобразовать все правила A -> w , где len (w)> 2, по правилам длины 2, содержащим свежие переменные.

Для вашего * 1013Правило * A , затем создайте правило для получения терминалов, скажем K -> a , и замените все вхождения терминала a :

A -> AKKK

Затем поместите грамматику в CNF

A    -> AA'
A'   -> KA''
A''  -> KK