Проектирование контекстной бесплатной грамматики [HW]

Question

Я работал над этим около 5 часов, выполняя домашнюю работу, и я надеялся, что некоторые из вас, ребята, смогут помочь, так как CFG - огромная часть CS.

Моя настоящая проблема с частьюC.

Разработка CFG для каждого из следующих языков:

A.{(a ^ i) (b ^ j) (c ^ k)} ГДЕ (i! = j) И i, j, k> = 0)

Я придумал:

Start-> aAB | AbB
A-> epsilon | aA
B-> epsilon | C | bB
C-> epsilon | cC

Кажется, это работает для bccc, abbcc, aabbb, cc, так что я думаю, что я здесь хорошо.

B.{(a ^ i) (b ^ j) (c ^ k)} ГДЕ (i! = k) И i, j, k> = 0)

Start-> aABC | ABcC
A-> epsilon | aA
B-> epsilon | bB
C-> epsilon | cC

Это работает для bc, bbcc,ab, abb, aac, поэтому все выглядит хорошо, когда i! = k

C.{(a ^ i) (b ^ j) (c ^ k)} ГДЕ (i! = j ИЛИ i! = k) И i, j, k> = 0)

Start-> aABC | AbB | ABcC
A-> epsilon | aA
B-> epsilon | bB | C
C-> epsilon | cC

Я делаюне думаю, что часть C верна, но я верю, что A и B верны.Может кто-нибудь сказать мне, если я прав / неправильно или помочь в любом случае?Я верю, что в последнем случае я просто делаю OR, и потому что мои переменные A, B, C почти одинаковы, я могу избежать комбинирования.Кажется, он работает, как bc работает, acc работает и многие другие, но у меня возникает ощущение, что я не должен просто комбинировать начальные состояния.

Кто-нибудь знает, прав я или близок, или у вас есть какие-либо советы?

Answer 1

Помните, что, когда вы тестируете грамматику, не забудьте также протестировать строки, которые должны быть отклонены (см. Ответ @ Paulo для некоторых, которые в настоящее время не работают). Чтобы решить первые два, напишите грамматику, которая представляет A^i B^j, где i != j; добавьте грамматику для произвольного числа c в конце этого для части 1, и добавьте эту грамматику в середину для части 2. Для части 3, помните, что объединение двух грамматик может быть легко записано как грамматика.

Answer 2

Ваша первая грамматика соответствует abc (от Пуск -> AbB -> abB -> abC -> abc), так что это неправильная грамматика.

Итак, вам нужно убедиться, что a s и b s создаются в одном и том же количестве (а затем еще несколько для одного из них).

То же abc также соответствует вашему второму правилу, где его не должно бытьразрешено тоже.