Построить CFG для

Question

L1 = {a ^ ib ^ j |i, j> = 0}

Моя попытка:

S = SA|e

A = aAB|e

B = bB|e

У меня нет возможности подтвердить свой ответ, это правильно?

Answer 1

Это неправильно, потому что нет способа получить один «b» (или любое количество «b» без «a»).

(И я думаю, что вы можете исправить это, изменив только одну букву; o)

PS Извините за ранее неправильный ответ; думал, что это для я = J.

Answer 2

Вы определяете L1 = {a ^ ib ^ j |i, j> = 0}.На словах это язык всех строк, которые начинаются с нуля или более а и заканчиваются нулями или более б.Это обычный язык;регулярное выражение для этого - * b *.Обычная грамматика (также не зависящая от контекста грамматика) выглядит следующим образом:

S := lambda | aS | bT
T := lambda | bT

Другая не зависящая от контекста грамматика выглядит следующим образом:

S := lambda | aS | Sb

Извините, если я что-то упустилВаш язык сложнее, чем я читаю.Если у вас есть основания полагать, что определение L1 отличается от языка, который я описал, объясните.