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

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