Даны три грамматики с начальным символом S:
Грамматика №1: S -> 1S11 | 1411
Грамматика №2: A -> BC B -> OB1 | 01 C -> 10C0 | C0 | 1000
Для грамматики №1 цепочки, порождаемые этой грамматикой, будут иметь следующий вид:
1^n1^m1411, где m, n > 0
Для грамматики №2 цепочки, порождаемые этой грамматикой, будут иметь следующий вид:
0^n(10)^m0, где m, n > 0
Объединим эти две формы в одну форму: 0^n(10)^m1411, где m, n > 0
Решение шаг за шагом:
1. Сначала выберем n количество ведущих нулей.
2. Затем добавим 1 символ и продолжим суммирование m количества “10”.
3. После этого добавим “1411” в конце каждой цепочки.
Примеры цепочек:
Для n=1 и m=1: 01010141111
Для n=2 и m=3: 001010101010141114111114111
и т. д.
Таким образом, язык, порождаемый данной грамматикой, является языком L={0^n(10)^m1411 | m, n > 0}, где n – количество ведущих нулей, m – количество “10”.