Преобразование CFG в форму Хомского Normal

  1. Используя лемму прокачки для обычных языков, покажите, что

    язык L = {ai, bj ck | i, j, k - неотрицательные целые числа, и i=j или i=k }

не регулярно

  1. Дизайн CFG для языка выше

Это то, что я придумал

Answer: G = (V,,R, S) with set of variables V = {S,W,X, Y,Z},
where S is the start variable; set of terminals  = {a, b, c}; and rules
S → XY | W
X → aXb | e
Y → cY | e
W → aWc | Z
Z → bZ | e

Теперь я должен преобразовать вышеупомянутый CFG в нормальную форму, с которой у меня возникают проблемы... любая помощь?

0 ответов

Другие вопросы по тегам