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

Ответ 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

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

Ответ 2

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

Бесконтекстная грамматика

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  |   })

Ответ 3

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

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

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

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

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

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

S -> AB.
S -> aB.

Теперь замените то, что A и B разложите на:

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 строк, генерируя много новых промежуточных переменных.