Опишите язык, созданный этой контекстно-свободной грамматикой - PullRequest
Новая
       12

Опишите язык, созданный этой контекстно-свободной грамматикой

0 голосов
/ 09 ноября 2018

У меня есть следующая грамматика,

  1. S -> Sb
  2. S -> aaSb
  3. S -> b

Типичные производные в этой грамматикеS => Sb => [aaSb]b => [aa[b]b]b => aabbb для n = 1S => Sb => [aaSb]b => [aa[aaSb]b]b => [aa[aabb]b]b => aaaabbbb для n = 2

Редактировать: Итак, я утверждал, что эта грамматика генерирует языкL = {a^(2n)b^(n+2) : n >= 1}

Я почти уверен, что мой a уходит a^(2n), поскольку есть два a до S, но как насчет b.Здесь нет лямбды, поэтому мой n идет от n >= 1?.

Редактировать:b^(n+1) и b^(2n+1) являются неверными предположениями, поскольку грамматика может получить строку aaaaaabbbbb, если n = 3.Я изменил свой b на b^(n+2).так что L становится L = {a^(2n)b^(n+2) : n >= 1}

Ответы [ 2 ]

0 голосов
/ 09 ноября 2018

Один из способов решения этой проблемы - переписать грамматику. Обратите внимание, что оба произведения 1 и 2 оканчиваются на Sb, поэтому мы можем оставить их с левым множителем: 

S -> ASb
S -> b
A -> 
A -> aa

Из первых двух постановок довольно легко увидеть, что S генерирует A^n b^{n+1} for n >= 0.

Из двух последних постановок A^n генерирует a^{2k} for 0 <= k <= n.

Так что язык a^{2k} b^{n+1} for n >= 0, 0 <= k <= n.

Или эквивалентно, пусть m = n - k для получения a^{2k} b^{k+m+1} for k,m >= 0.

0 голосов
/ 09 ноября 2018

Язык, генерируемый этой грамматикой, - a^(2n) b^(n+m+1), где n и m - натуральные числа. Чтобы показать это, (а) мы видим, что любая строка, полученная с использованием произведений грамматики, соответствует вышеуказанному, и (б) любая строка, соответствующая вышеприведенному, может быть получена с использованием произведений грамматики.

(a) Грамматика может и должна использовать правило (3) ровно один раз. Это дает +1 в количестве b с. Выполнение правила (2) может происходить несколько раз n, помещая 2n a с впереди и n b с сзади, следовательно, термины 2n и n. Правило (1) может быть выполнено любое количество раз m, отсюда и термин.

(b) Дана строка a^(2n) b^(n+m+1) для натуральных чисел n и m: используйте правило (1) количество раз, равное m; затем используйте правило (2) количество раз, равное n; затем пользовательское правило (3) один раз. Таким образом, грамматика порождает строку.

Другой способ написать тот же ответ - a^2n b^m с m > n.

...