0
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

You can prove grammar equivalence by showing that they represent the same language,use fixed pont iteration method to find language of context free grammar.

$\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.