GRAMMARS CFG derivation language help! 1) Do the grammars of both the CFG\'s lis
ID: 3932069 • Letter: G
Question
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
Explanation / Answer
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.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.