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

Question

Переведите приведенную ниже грамматику в нормальную форму Хомского. Дайте все промежуточные шаги.

S -> AB | aB
A -> aab|lambda
B -> bbA

Хорошо, первое, что я сделал, это добавил новую стартовую переменную S0

так что теперь у меня есть

S0 -> S
S -> AB | aB
A -> aab|lambda
B -> bbA

затем я удалил все лямбда-правила:

S0 -> S
S -> AB | aB | B
A -> aab
B -> bbA | bb

Затем я проверил правила типа S->S и A->B, которых не было. И это был ответ, который я придумал, нужно ли мне что-то делать дальше или я сделал что-то не так?

Answer 1

Википедия говорит:

В информатике говорят, что не зависящая от контекста грамматика имеет нормальную форму Хомского, если все ее правила производства имеют вид:

• A -> BC , или
• A -> α, или
• S -> ε

, где A , B , C - нетерминальные символы, α - терминальный символ, S - начальный символ, а ε - пустая строка.Кроме того, ни B , ни C не могут быть начальным символом.

Продолжение вашей работы:

S0 -> S
S -> AB | aB | B
A -> aab
B -> bbA | bb

Вместо использования | для обозначения различных вариантов разделите правило на несколько правил.

S0 -> S
S -> AB
S -> aB
S -> B
A -> aab
B -> bbA
B -> bb

Создайте новые правила Y -> a и Z -> b, потому что они нам понадобятсяскоро.

S0 -> S
S -> AB
S -> aB
S -> B
A -> aab
B -> bbA
B -> bb
Y -> a
Z -> b

S -> aB не имеет форму S -> BC, потому что a является терминалом.Поэтому измените a на Y:

S0 -> S
S -> AB
S -> YB
S -> B
A -> aab
B -> bbA
B -> bb
Y -> a
Z -> b

Сделайте то же самое для правила B -> bb:

S0 -> S
S -> AB
S -> YB
S -> B
A -> aab
B -> bbA
B -> ZZ
Y -> a
Z -> b

Для A -> aab создайте C -> YY;для B -> bbA создайте D -> ZZ:

S0 -> S
S -> AB
S -> YB
S -> B
A -> CZ
C -> YY
B -> DA
D -> ZZ
B -> ZZ
Y -> a
Z -> b

Для S -> B, продублируйте одно правило, где S находится справа, и вставьте правило:

S0 -> B
S0 -> S
S -> AB
S -> YB
A -> CZ
C -> YY
B -> DA
D -> ZZ
B -> ZZ
Y -> a
Z -> b

Разобраться с правилами S0 -> B и S0 -> S, соединив правую сторону с левой стороной других правил.Кроме того, удалите осиротевшие правила (где символ LHS никогда не используется в RHS):

S0 -> DA
S0 -> ZZ
S0 -> AB
S0 -> YB
A -> CZ
C -> YY
B -> DA
D -> ZZ
B -> ZZ
Y -> a
Z -> b

И все готово.Уф!

Answer 2

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

---

Грамматика без контекста

G(Variables = { A B S }
Start = S 
Alphabet = { a b lamda}

Production Rules = { 
S  ->  |  AB  |  aB  |  
A  ->  |  aab  |  lamda  |  
B  ->  |  bbA  |   } )

Удалить лямбда / эпсилон

ERRASABLE(G) = { A }

G(Variables = { A S B }
Start = S
Alphabet = { a b }

Production Rules = { 
S  ->  |  AB  |  aB  |  B  | 
B  ->  |  bbA  |  bb  |   } )

Удалитьединица продукции

UNIT(A) { A }
UNIT(B) { B }
UNIT(S) { B S }
G (Variables = { A B S }
Start = S 
Alphabet = { a b }

Production Rules = { 
S  ->  |  AB  |  aB  |  bb  |  bbA  |  
A  ->  |  aab  |  
B  ->  |  bbA  |  bb  |   })

Определить живые символы

LIVE(G) = { b A B S a }

G(Variables = { A B S }
Start = S
Alphabet = { a b }

Production Rules = { 
S  ->  |  AB  |  aB  |  bb  |  bbA  |  
A  ->  |  aab  |  
B  ->  |  bbA  |  bb  |   })

Удалить недоступные

REACHABLE (G) = { b A B S a }
G(Variables = { A B S }
Start = S 
Alphabet = { a b }

Production Rules = { 
S  ->  |  AB  |  aB  |  bb  |  bbA  |  
A  ->  |  aab  |  
B  ->  |  bbA  |  bb  |   })

Заменить все смешанные строки сплошными нетерминалами

G( Variables = { A S B R I }
Start = S
Alphabet = { a b }

Production Rules = { 
S  ->  |  AB  |  RB  |  II  |  IIA  |  
A  ->  |  RRI  |  
B  ->  |  IIA  |  II  |  
R  ->  |  a  |  
I  ->  |  b  |   })

Хомская нормальная форма

G( Variables = { V A B S R L I Z }
Start = S 
Alphabet = { a b }

Production Rules = { 
S  ->  |  AB  |  RB  |  II  |  IV  |  
A  ->  |  RL  |  
B  ->  |  IZ  |  II  |  
R  ->  |  a  |  
I  ->  |  b  |  
L  ->  |  RI  |  
Z  ->  |  IA  |  
V  ->  |  IA  |   })

Answer 3

Альтернативный ответ: грамматика может давать только конечное число строк, а именно 6.

 S -> aabbbaab | aabbb | bbaab | bb | abbaab | abb.

Теперь вы можете сжать это обратно в нормальную форму Хомского вручную.

---

Подстановкой мы можем найти множество всех произведенных строк. Ваши начальные правила:

S -> AB | aB.
A -> aab | lambda.
B -> bbA.

Сначала разделите правило S:

S -> AB.
S -> aB.

Теперь подставим то, во что А и В расширяются:

S -> AB
  -> (aab | lambda) bbA
  -> (aab | lambda) bb (aab | lambda).
S -> aB
  -> abbA
  -> abb (aab | lambda).

Разверните их снова, чтобы получить:

S -> aabbbaab.
S -> aabbb.
S -> bbaab.
S -> bb.
S -> abbaab.
S -> abb.

---

Чтобы изменить этот конечный набор на нормальную форму Хомского, достаточно сделать это грубой силой без какого-либо разумного факторинга. Сначала мы вводим два терминальных правила:

X -> a.
Y -> b.

Теперь для каждой строки мы используем первую букву с терминальной переменной, а остальные буквы с новой переменной. Например, вот так:

S -> aabbb. (initial rule, not in Chomsky Normal Form)

S -> XC, where X->a and C->abbb.
C -> XD, where X->a and D->bbb.
D -> YE, where Y->b and E->bb.
E -> YY, where Y->b and Y->b.

Мы просто проходим этот процесс для всех 6 строк, генерируя много новых промежуточных переменных.