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

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, содержащим свежие переменные.

Для Вашего правило, тогда, построить правило для получения терминалов, скажем K -> а, и заменить все вхождения терминала :

A -> AKKK 

Затем положить грамматику в CNF

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