CFG находится в нормальной форме Хомского, если продукция находится в следующих формах —
- А → а
- A → BC
- S → ε
где A, B и C не являются терминалами, а a являются терминалами.
Алгоритм преобразования в нормальную форму Хомского —
Шаг 1 — Если начальный символ S встречается справа, создайте новый начальный символ S ‘ и новый производственный S’ → S.
Шаг 2 — Удалить нулевые произведения. (Использование алгоритма удаления продукции Null, обсуждавшегося ранее)
Шаг 3 — Удалить единицу продукции. (Использование алгоритма удаления производства блока обсуждалось ранее)
Шаг 4 — Заменить каждое производство A → B 1 … B n, где n> 2, на A → B 1 C, где C → B 2 … B n . Повторите этот шаг для всех произведений, имеющих два или более символов в правой части.
Шаг 5 — Если правая сторона любого производства имеет вид A → aB, где a является терминалом, а A, B нетерминальным, то производство заменяется на A → XB и X → a . Повторите этот шаг для каждого производства, которое имеет вид A → aB .
проблема
Конвертировать следующие CFG в CNF
S → ASA | aB, A → B | S, B → b | ε
Решение
(1) Поскольку S появляется в RHS, мы добавляем новое состояние S 0, а S 0 → S добавляется в производственный набор, и оно становится —
S 0 → S, S → ASA | aB, A → B | S, B → b | ∈
(2) Теперь мы удалим нулевые произведения —
B → ∈ и A → ∈
После удаления B → ε производственный набор становится —
S 0 → S, S → ASA | АБ | a, A → B | S | ∈, B → b
После удаления A → ∈ производственный набор становится —
S 0 → S, S → ASA | АБ | а | AS | SA | S, A → B | S, B → b
(3) Теперь мы удалим единицу продукции.
После удаления S → S, производственный набор становится —
S 0 → S, S → ASA | АБ | а | AS | SA, A → B | S, B → b
После удаления S 0 → S, производственный набор становится —
S 0 → ASA | АБ | а | AS | SA, S → ASA | АБ | а | AS | SA
A → B | S, B → b
После удаления A → B производственный набор становится —
S 0 → ASA | АБ | а | AS | SA, S → ASA | АБ | а | AS | SA
A → S | б
B → b
После удаления A → S производственный набор становится —
S 0 → ASA | АБ | а | AS | SA, S → ASA | АБ | а | AS | SA
A → b | ASA | АБ | а | AS | SA, B → b
(4) Теперь мы узнаем более двух переменных в RHS
Здесь S 0 → ASA, S → ASA, A → ASA нарушает два нетерминала в RHS
Следовательно, мы применим шаг 4 и шаг 5, чтобы получить следующий конечный производственный набор, который находится в CNF —
S 0 → AX | АБ | а | AS | SA
S → AX | АБ | а | AS | SA
A → b | AX | АБ | а | AS | SA
B → b
X → SA
(5) Мы должны изменить произведения S 0 → aB, S → aB, A → aB
И окончательный комплект производства становится —
S 0 → AX | YB | а | AS | SA
S → AX | YB | а | AS | SA
A → b A → b | AX | YB | а | AS | SA
B → b
X → SA
Y → a