Построение Язык порождена грамматикой

Question

Мы должны найти L (G), где грамматика G дается как-

S-> AB | CD, A-> аА | а, B-> Б.Б. | Британская Колумбия, C-> ЧЖД | d, d> AD | AD

Я попытался вопрос, но он рекурсии очень глубоко и я не могу прекратить строку [Я знаю, что будет генерировать. a^n после n шагов, но как насчет D, C, B?]

До сих пор я сделал следующее:

A->aA->aaA->....->a^(n-1)A (after n-1 steps)->a^n 
B->bB->bbB->....->b^(m-1)B (after m-1 steps)->b^(m-1)bC->b^(m-1)bbC->...b^(m-1)b^(n-1)C->b^kC 
C->cD->ccD->...->c^(p-1)D or c^(p-1)d[Thus we will consider as C->c^pD or C->c^pd] 
D->aD->aaD->...->a^(q-1)D->a^(q-1)a^nD[Thus we will consider D->a^rD] 

Теперь B зависит от C и C зависит от D и D зависит от себя (D рецидивирует IE-на себя как D-> а^гв)

Так как я могу найти грамматику для этого язык, который не заканчивается?

Answer 1

D не дает строку терминалов, так что это не имеет смысл и может быть опущен в том числе всех правил, которые имеют D.

Упрощенная грамматика бы:

S->AB, A->aA|a ,B->bB|bC, C->d 

И язык будет : {a^mb^nd: m, n> = 1}