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

Question

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

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

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

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

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

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

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

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

Answer 1

Чтобы начать преобразование в нормальную форму Хомского (используя Определение (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'' по сути не является контрактной;теперь вы можете применить оставшиеся алгоритмы к грамматике, чтобы найти эквивалентную грамматику в нормальной форме Хомского.

Answer 2

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