Конвертировать грамматику в обычную форму Хомского

Question

S -> A | ABa | AbA

A -> Aa | lambda

B -> Bb | BC

C -> CB | CA | bB

Мне нужна помощь, чтобы сменить эту грамматику на обычный хомский. Это ответ, который я придумал, но я привел его к своему профессору, и он посоветовал мне, что это неправильно. Он отказался сказать мне, как исправить это, потому что его нужно снова включить в класс. Вся помощь приветствуется.

GL: S → ZA | AW A → AA | a B → AX | YY Z → a Y → b X → YB W → BZ

Answer 1

Мои знания могут быть ржавыми, но я постараюсь помочь.

Согласно википедии,

В теории формальных языков, контекстно-свободная грамматика называется в нормальной форме Хомского, если все ее правила производства имеют вид:

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

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

Я рассматриваю вашу лямбду - это epsilon ε. Давайте перефразировать вашу грамматику

S -> A 
S -> ABa 
S -> AbA 
A -> Aa 
A -> ε 
B -> Bb 
B -> BC 
C -> CB 
C -> CA 
C -> bB 

Затем добавьте новую переменную S0 в качестве новой переменной старта, поэтому она становится

S0 -> S 
S -> A 
S -> ABa 
S -> AbA 
A -> Aa 
A -> ε 
B -> Bb 
B -> BC 
C -> CB 
C -> CA 
C -> bB 

Затем удалите ε правила, поэтому он становится

S0 -> S 
S -> A 
S -> ABa 
S -> AbA 
A -> Aa 
B -> Bb 
B -> BC 
C -> CB 
C -> CA 
C -> bB 

Ввести новую переменную Y->a и Z->b.

S0 -> S 
S -> A 
S -> ABa 
S -> AbA 
A -> Aa 
B -> Bb 
B -> BC 
C -> CB 
C -> CA 
C -> bB 
Y -> a 
Z -> b 

Переписать правила RHS:

S0 -> S 
S -> A 
S -> ABY 
S -> AZA 
A -> AY 
B -> BZ 
B -> BC 
C -> CB 
C -> CA 
C -> ZB 
Y -> a 
Z -> b 

ввести новую переменную D->AB и E->AZ, поэтому она становится

S0 -> S 
S -> A 
S -> DY 
S -> EA 
A -> AY 
B -> BZ 
B -> BC 
C -> CB 
C -> CA 
C -> ZB 
D -> AB 
E -> AZ 
Y -> a 
Z -> b 

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

S0 -> S 
S0 -> A 
S -> DY 
S -> EA 
A -> AY 
B -> BZ 
B -> BC 
C -> CB 
C -> CA 
C -> ZB 
D -> AB 
E -> AZ 
Y -> a 
Z -> b 

Объедините правило для S0 и S.

S0 -> DY 
S0 -> EA 
S0 -> AY 
A -> AY 
B -> BZ 
B -> BC 
C -> CB 
C -> CA 
C -> ZB 
D -> AB 
E -> AZ 
Y -> a 
Z -> b 

Теперь у нас есть грамматика в обычной форме хомского.