Регулярные грамматики

Question

В обычной грамматике со следующими правилами S->aS/aSbS/ε допустимо ли выполнять следующие шаги: S->aSbS->a{aSbS}bS->aa{aSbS}bSbS->aaa{aSbS}bSbSbS

Должен ли я заменить каждый S на каждом шаге или я могу заменить один S из двух, например? В этом: aSbS я могу сделать aSb (следуя правилу S->ε), и если я не могу, я должен заменить все S с тем же правилом? (aSbS)-> a(aS)b(aS) (следуя правилу (S-> aS)) или я могу сделать (aSbS->a(aS)b(aSbS)) .

пс. Я использую скобки, которые указывают, какие S я заменил

Answer 1

В формальной грамматике шаг деривации состоит в замене одного экземпляра левой части правила на правую часть этого правила. В случае контекстно-свободной грамматики левая часть представляет собой один нетерминал, поэтому этап деривации состоит в замене одного экземпляра нетерминала одной из возможных соответствующих правых частей.

Вы никогда не выполняете две замены одновременно, и каждый шаг деривации не зависит от любого другого шага деривации, поэтому в грамматике без контекста нет способа выразить ограничение, что два нетерминала должны быть заменены одним и тем же Правая сторона. (На самом деле вы не можете напрямую выразить это ограничение с помощью контекстно-зависимой грамматики, но вы можете добиться эффекта с помощью маркеров.)

Регулярные грамматики - это подмножество контекстно-свободных грамматик, где любая правая часть, включающая нетерминал, имеет вид aC или каждая правая часть, которая включает в себя нетерминал, имеет вид Ba, (Это прямо из страницы Википедии, на которую вы ссылаетесь.) Ваша грамматика не является обычной грамматикой, потому что правило S → aSbS имеет два нетерминала на правой стороне, что не является ни одной из обычных форм.