2

So I'm given the grammar $$P ::= id | P ∨ P | P ∧ P | ¬P | (P)$$ $$id ::= p | q | r | s$$

and was asked to rewrite it as unambiguous. The solution says it is $$P ::= P ∨ Q | P ∧ Q | Q$$ $$Q ::= id | ¬Q | (P)$$ $$id ::= p | q | r | s$$

but using the latter unambiguous grammar, I can't figure out how I would get a derivation for $¬(p ∧ q)$

my attempt was P => P∧Q => Q∧Q => ¬Q∧Q

but I can't figure out how to get the parens around the Q∧Q

greenteam
  • 333

2 Answers2

1

Working from the outside in:

$P \implies Q \implies \lnot Q \implies \lnot (P) \implies \lnot (P\wedge Q) \implies \lnot (P\wedge id) \implies \lnot (P\wedge q) \implies \lnot (Q \wedge q) \implies \lnot (id \wedge q) \implies \lnot (p \wedge q).$

Parentheses have to be introduced via $Q::=(P),$ because that's the only clause in the grammar that includes parentheses.

Mitchell Spector
  • 9,917
  • 3
  • 16
  • 34
1

You can take the following path:

P => Q => ~Q => ~(P) => ~(P ∧ Q) => ~(Q ∧ Q) => ~(id ∧ Q) => ~(p ∧ Q) => ~(p ∧ id) => ~(p ∧ q).

AbelianGrape
  • 113