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

Question

Мне нужна твоя помощь У меня есть эти постановки:

1) A--> aAb
2) A--> bAa
3) A--> ε

Я должен применить нормальную форму Хомского (CNF).

Чтобы применить вышеупомянутое правило, я должен:

1. устранить ε производства
2. ликвидировать унитарные производства
3. удалить ненужные символы

Сразу застрял. Причина в том, что A является обнуляемым символом (ε является частью его тела)

Конечно, я не могу удалить символ.

Может ли кто-нибудь помочь мне получить окончательное решение?

Answer 1

Как отмечает Википедия, есть два определения нормальной формы Хомского, которые отличаются в трактовке ε-продукций. Вам придется выбрать тот, где они разрешены, иначе вы никогда не получите эквивалентную грамматику: ваша грамматика создает пустую строку, в то время как грамматика CNF, следующая за другим определением, не способна на это.

Answer 2

Чтобы начать преобразование в нормальную форму Хомского (используя Определение (1), предоставленное страницей Википедии), вам нужно найти эквивалентную по существу неконтрактную грамматику. Грамматика G с начальным символом S по существу не заключая контракт, если

1. S is not a recursive variable
2. G has no ε-rules other than S -> ε if ε ∈ L(G)

Называя вашу грамматику Gэквивалентная грамматика G' с нерекурсивным начальным символом:

G' : S -> A
     A -> aAb | bAa | ε

Понятно, что множество обнуляемых переменных G' является {S,A}, поскольку A -> ε это производство в G' а также S -> A это цепное правило. Я предполагаю, что вам дан алгоритм удаления ε-правил из грамматики. Этот алгоритм должен производить грамматику, похожую на:

G'' : S -> A | ε
      A -> aAb | bAa | ab | ba

Грамматика G'' является по существу неконтрактным; Теперь вы можете применить оставшиеся алгоритмы к грамматике, чтобы найти эквивалентную грамматику в нормальной форме Хомского.