Контекстная грамматика для определенного языка

Question

Я не могу понять простую проблему. Я должен указать грамматику для следующих слов

а) (ab)^2i c, i>=1

для г = 1 ababc для г = 2 ababababc

S -> abA 
    A -> ab | abc | c 

б) a^(m-1) b^(m+1) a^n b^n, m>=1 n>=1

для I = 1 bbab для i = 2 abbbaabb

S -> AbbAaAb 
    A -> ba | ab | a 

Может кто-нибудь проверить эти упражнения и дать мне обратную связь. Что я делаю не так?

Answer 1

Первый из них будет генерировать (ab)^i, и вы просто хотите четное число ab пар слов, так что вы должны определить его как

S -> ababA 
A -> ababA | c 

Вы также должны использовать A на правой стороне, в второе правило, как ваши правила будут создавать слово длины макс 5.

второй один

S -> AbbB 
A -> aAb | epsilon (empty string) 
B -> aAb 

Для первой части слово, вам всегда нужно bb с правой стороны. Вы генерируете a^n b^n слева от него.

Для второй части слова, мы повторно нетерминал A, но мы уверены, что есть по крайней мере один ab в словесной части - вот почему B.