CODEWITHSUNDEEP
grammarcomputation-theory
user7475343
user7475343

Reputation:

Regular grammars

In a regular grammar with the following rules S->aS/aSbS/ε is it acceptable to do the following steps: S->aSbS->a{aSbS}bS->aa{aSbS}bSbS->aaa{aSbS}bSbSbS

Do i have to replace every S in each step or i can replace one S out of two for example? In this : aSbS can i do aSb (following the rule S->ε) and if i cannot should i replace all the S's with the same rule? (aSbS)-> a(aS)b(aS) (following the rule (S->aS) ) or i can do (aSbS->a(aS)b(aSbS)) .

ps. I use the parentheses do indicate which S's i have replaced

Upvotes: 0

Views: 161

Answers (1)

rici
rici

Reputation: 241671

In a formal grammar, a derivation step consists of replacing a single instance of the left-hand side of a rule with the right-hand side of that rule. In the case of a context-free grammar, the left-hand side is a single non-terminal, so a derivation step consists of replacing a single instance of a non-terminal with one of the possible corresponding right-hand sides.

You never perform two replacements at the same time, and each derivation step is independent of every other derivation step, so in a context-free grammar, there is no way to express the constraint that two non-terminals need to be replaced with the same right-hand side. (In fact, you cannot directly express this constraint with a context-sensitive grammar either, but you can achieve the effect by using markers.)

Regular grammars are a subset of context-free grammars where either every right-hand side which includes a non-terminal has the form aC or every right-hand side which includes a non-terminal has the form Ba. (This comes straight out of the Wikipedia page which you link.) Your grammar is not a regular grammar, because the rule S → aSbS has two non-terminals on the right-hide side, which is not either of the regular forms.

Upvotes: 1

Related Questions