# Proving grammar equivalence in simple grammar (generate any sequence of three characters)

Goal is proving grammar equivalence

Upper-case symbols are non-terminal.

Lower-case symbols are terminal.

The start symbol is S.

A grammar production rule is non-terminals-only if it only contains non-terminals. For example: AB -> CDE

A grammar rule is non-terminal-to-terminal if the left side has one non-terminal and the right side has one terminal. For example: A -> a B -> b

A grammar is aterminal if:

• The number of terminals equals the number of non-terminals
• All rules are non-terminals-only or non-terminal-to-terminal
• Each non-terminal has a corresponding terminal via a non-terminal-to-terminal rule (and each terminal appears exactly once in a non-terminal-to-terminal rule)

For example:

Grammar 1

S -> SS
S -> A

S -> s
A -> a


It's called aterminal, because, in some sense, there's no distinction between terminals and non-terminals.

All grammars in this question are unrestricted, but aterminal.

If you start with a sequence of symbols, and use multiple production rules to generate a new sequence of symbols, you can consider that an additional (but redundant) rule.

For example:

Grammar 2:

A -> BB
B -> CC
C -> AA

A -> a
B -> b
C -> c


If we start with a non-terminal B:

B (we happen to start with B)
CC (B -> CC)
AAC (C -> AA)
AAAA (C -> AA)


Therefore we can add B -> AAAA to the grammar without changing the language it recognizes.

Grammar 3

S -> SS
S -> A
S -> B

S -> s
A -> a
B -> b


Grammar 3 generates any (non-empty) sequence of s,a and b. For example, to generate sab:

S (start rule)
SS (S -> SS)
SSS (S -> SS)
SAS (S -> A)
SAB (S -> B)
sAB (S -> s)
saB (A -> a)
sab (B -> b)


Grammar 4

S -> SS
S -> A
AA -> B

S -> s
A -> a
B -> b


Using the idea from Grammar 2, we can start with S and derive:

S (happen to start with S)
SS (S -> SS)
AS (S -> A)
AA (S -> A)
B (AA -> B)


Therefore we can derive S -> B as an additional rule.

I believe now, having add S -> B, we can remove AA -> B and thus Grammars 3 and 4 are equivalent, but I don't know how to prove this. Is this right??? If so, what's the proof???

Here's my progress:

Additionally, we can derive S -> AA.

Now we have three rules of this form:

X -> Y
Y -> Z
X -> Z


Namely:

S -> AA
AA -> B
S -> B


Maybe when you have 3 rules of this form, AND the only way to get Y is by "first going through X", then you can remove the Y -> Z rule. I don't know if this is right or how to formalize this.