GRAMMARS CFG derivation language help 1 Do the grammars of b

GRAMMARS CFG derivation language help!

1) Do the grammars of both the CFG\'s listed below define the same language? 2) Please explain how you know.

Here is my complete derivation of both CFG\'s.

Given the following CFG, show a derivation of the following expressions:

3 + 4 * 5 + 7

(3 + 4) * (5 + 7) * 8

1) START       ::= AE

2) AE              ::= AE + AE

3) AE              ::= AE * AE

4) AE              ::= (AE)

5) AE              ::= number       (n = number) “For space purposes.”

1. S => AE

3. => AE * AE

2. => AE + AE * AE

5. => n + AE * AE

5. => n + n * AE

2. => n + n * AE + AE

5. => n + n * n + AE

5. => n + n * n + n

1. S => AE

3. => AE * AE

3. => AE * AE * AE

4. => (AE) * AE * AE

2. => (AE + AE) * AE * AE

5. => (n + AE) * AE * AE

5. => (n + n) * AE * AE

4. => (n + n) * (AE) * AE

2. => (n + n) * (AE + AE) * AE

5. => (n + n) * (n + AE) * AE

5. => (n + n) * (n + n) * AE

5. => (n + n) * (n + n) * n

Given the following CFG, show a derivation of the following expressions:

3 + 4 * 5 + 7

(3 + 4) * (5 + 7) * 8

1) START       ::= EXPR

2) EXPR         ::= FACT + EXPR

3) EXPR         ::= FACT

4) FACT         ::= (EXPR)

5) FACT         ::= FACT * FACT

6) FACT         ::= number                (n = number) “For space purposes.”

1. S => EXPR

2. => FACT + EXPR

6. => n + EXPR

2. => n + FACT + EXPR

5. => n + FACT * FACT + EXPR

6. => n + n * FACT + EXPR

6. => n + n * n + EXPR

3. => n + n * n + FACT

6. => n + n * n + n

1. S => EXPR

3. => FACT

5. => FACT * FACT

4. => (EXPR) * FACT

2. => (FACT + EXPR) * FACT

6. => (n + EXPR) * FACT

3. => (n + FACT) * FACT

6. => (n + n) * FACT

5. => (n + n) * FACT * FACT

4. => (n + n) * (EXPR) * FACT

2. => (n + n) * (FACT + EXPR) * FACT

6. => (n + n) * (n + EXPR) * FACT

3. => (n + n) * (n + FACT) * FACT

6. => (n + n) * (n + n) * FACT

6. => (n + n) * (n + n) * n

Given the following CFG, show a derivation of the following expressions: 3 + 4 * 5 + 7 (3 + 4) * (5 + 7) * 8 1) START       ::= AE 2) AE              ::= AE + AE 3) AE              ::= AE * AE 4) AE              ::= (AE) 5) AE              ::= number       (n = number) “For space purposes.”

1. S => AE 3. => AE * AE 2. => AE + AE * AE 5. => n + AE * AE 5. => n + n * AE 2. => n + n * AE + AE 5. => n + n * n + AE 5. => n + n * n + n 1. S => AE 3. => AE * AE 3. => AE * AE * AE 4. => (AE) * AE * AE 2. => (AE + AE) * AE * AE 5. => (n + AE) * AE * AE 5. => (n + n) * AE * AE 4. => (n + n) * (AE) * AE 2. => (n + n) * (AE + AE) * AE 5. => (n + n) * (n + AE) * AE 5. => (n + n) * (n + n) * AE 5. => (n + n) * (n + n) * n

Solution

Yes. To get a number definitely we should use 3) EXPR ::= FACT. So, if we replace EXPR with FACT in all places, grammar will be as given below

1) START ::= FACT
2) FACT ::= FACT + FACT
4) FACT ::= (FACT)
5) FACT ::= FACT * FACT
6) FACT ::= number

This grammar is as same as the former one. That\'s the reason why these both are same.