2
$\begingroup$

I am doing a course in uni on Automata and Formal Languages, and I think I've come across a pretty significant misunderstanding. When you have a rewrite rule in a grammar, and apply it to a string, do all occurrences of the string on the LHS get rewritten?

For example, if I have the string $abbababc$ over alphabet $\{a,b,c\}$, and rewrite rule $a \to b$ the string $bbbbbbbc$, or could we have also $bbababc$ and $bbbbbabc$, etc.

I thought it was the case that we could have only the first option but reading this answer: CFG of all regular expressions over a binary alphabet has made me think maybe differently.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
10
$\begingroup$

Probably your course teaches the context-free grammar. Indeed, in a CFG one position in the string is chosen, and the symbol at that position is rewritten using one of the rewrite rules. In a CFG the order of rewrites does not matter, the final result will be the same. (Provided the same rule is used at the respective positions, of course.)

Also note that in a CFG we usually distinguish between variables and terminal symbols. The variables can be rewritten, and the terminals appear in the final string.

There are variants of rewriting systems though. One also considers L systems, where all symbols in the string are rewritten at the same time. Those grammars are motivated by biological processes. They define a completely different class of formal languahes than those defined by context-free grammars.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Cheers. I have no clue how I have gone so long without realising this. $\endgroup$
    – I have Your Clock
    Commented Sep 4 at 13:43
1
$\begingroup$

Rewriting systems usually apply each rule once, sequentially. The left hand side might match at several points, in which case any match could be taken,

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.