Below is a CFG for boolean formulae written in prefix form. The terminal symbols

Question

Below is a CFG for boolean formulae written in prefix form. The terminal symbols in this language are = {f, t, , , ¬} having the following meanings:

f, t : these correspond to constants FALSE and TRUE.

: this is the OR operator

: the AND operator

¬: the negation operator

The AND and OR operators are both binary operators (two operands) and the negation operator is unary.

Ef|t

E EE

E EE

E ¬E

A: Consider the following formula in infix notation Rewrite this formula in prefix notation.

B: Show how your answer to II.A can be generated by the grammar above. Do this by showing a left-first derivation parse-tree.

C: Can you find an alternate left-first derivation for this string? In other words, is the grammar ambiguous?

D: Design a DPDA accepting this language.

Explanation / Answer

E -> f|t

E -> f

E -> t

E -> OR(ft) -> False OR True -> False

E -> AND(ft) -> False AND True -> True

E -> !t|f

E -> ! true

E -> ! false

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.