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

Question

Я пытаюсь построить CFG в нормальной форме Хомского с максимально возможным количеством произведений, которые допускают язык, содержащий единственную строку a^21.

Я понимаю, что я мог бы просто преобразовать

S -> AAAAAAAAAAAAAAAAAAAAA А -> а

но есть ли другой способ сократить этот язык затем преобразовать его в нормальной форме Хомского?

Answer 1

Мы можем довольно легко показать, что нам нужно по крайней мере шесть символов, чтобы надеяться создать CFG в CNF для этого языка, признав, что мы можем в лучшем случае удвоить сгенерированную длину строки с каждой постановкой, и мы должны начать с 2^0:

A_21 := ... 
A_16 := A_16 A_16 
A_8 := A_4 A_4 
A_4 := A_2 A_2 
A_2 := A_1 A_1 
A_1 := a 

Затем мы можем показать, что в CNF нет грамматики с шестью произведениями, которые генерируют наш целевой язык. Мы начинаем рассуждать, строя грамматику снизу вверх.

1. У нас должно быть A_1 := a, чтобы получить любые строки.
2. Мы должны A_2 := A_1 A_1 получить любую строку с длиной больше 1.
3. Теперь мы можем генерировать либо A_3 или пропустить что и генерировать A_4, или обоих. Рассмотрим каждый из этих случаев ниже.

Случай 1: A_3

1. Добавляет A_3 := A_2 A_1.
2. У нас уже есть 3 производства, и мы знаем, что нам нужна одна из форм A_21 := X Y. Таким образом, мы можем добавить еще два. Даже если мы добавим самые большие производственные мощности, которые теперь возможны - A_6 и A_12 - мы не можем производить A_21 по мере необходимости (мы можем изготовить не более A_18 := A_6 A_12. Поэтому добавление A_3 не может получить нам грамматику, которая генерирует наш язык в шести постановках.

Случай 2:... A_4

1. Добавляем A_4 := A_2 A_2
2. у нас уже есть 3 производств, и знаем, что нужно один вид A_21 := X Y Таким образом, мы можем добавить до более двух Наша Optio ns в настоящее время составляют A_5, A_6 и A_8. A_5 и A_6 по той же причине, о которой мы говорили выше для случая 1. A_8, однако, не подводит к этому рассуждению, поэтому мы добавляем A_8 := A_4 A_4.
3. Теперь у нас есть только одна продукция, и она должна быть либо A_20, A_19, A_17, либо A_13. Мы не можем сгенерировать ни одно из них, используя наши существующие постановления.

Мы таким образом исключили грамматику с 6 постановками. Если вы попытаетесь найти грамматику с 7 произведениями, используя приведенные выше рассуждения, вы найдете несколько. Поскольку мы знаем, что в CNF есть грамматики с 7 постановками, а у вас нет 6, вы закончили.Вот несколько из 7-этажных грамматик:

S := A_18 A_3 
A_18 := A_9 A_9 
A_9 := A_6 A_3 
A_6 := A_3 A_3 
A_3 := A_2 A_1 
A_2 := A_1 A_1 
A_1 := a 

S := A_17 A_4 
A_17 := A_9 A_8 
A_9 := A_8 A_1 
A_8 := A_4 A_4 
A_4 := A_2 A_2 
A_2 := A_1 A_1 
A_1 := a 

S := A_16 A_5 
A_16 := A_8 A_8 
A_8 := A_4 A_4 
A_5 := A_4 A_1 
A_4 := A_2 A_2 
A_2 := A_1 A_1 
A_1 := a 

S := A_15 A_6 
A_15 := A_9 A_6 
A_9 := A_6 A_3 
A_6 := A_3 A_3 
A_3 := A_2 A_1 
A_2 := A_1 A_1 
A_1 := a 

S := A_14 A_7 
A_14 := A_7 A_7 
A_7 := A_4 A_3 
A_4 := A_3 A_1 
A_3 := A_2 A_1 
A_2 := A_1 A_1 
A_1 := a 

S := A_13 A_8 
A_13 := A_8 A_5 
A_8 := A_5 A_3 
A_5 := A_3 A_2 
A_3 := A_2 A_1 
A_2 := A_1 A_1 
A_1 := a 

S := A_12 A_9 
A_12 := A_9 A_3 
A_9 := A_6 A_3 
A_6 := A_3 A_3 
A_3 := A_2 A_1 
A_2 := A_1 A_1 
A_1 := a 

S := A_11 A_10 
A_11 := A_10 A_1 
A_10 := A_8 A_2 
A_8 := A_4 A_4 
A_4 := A_2 A_2 
A_2 := A_1 A_1 
A_1 := a 

И есть еще много. Жесткая часть показывала, что не было никаких 6 постановок.