Question

A fully parenthesized arithmetic expression is defined recursively as:

(a) A natural number expressed in decimal notation (e.g., 0, 4, 357, but not 007).

(b) (α+β) or (α∗β), whereαandβare fully parenthesized arithmetic expressions.

Define a CFG that generates the following language over {0,1,...,9,(,),∗,+,o,d,e,v,n}:

L={α odd:αis a fully parenthesized arithmetic expression with an odd value}

∪ {α even:αis a fully parenthesized arithmetic expression with an even value}

For example, “75 odd”, “((241∗2) + 40034) even” are strings in the language (ignore the blank spaces in the strings, they are just there for clarity).

Answer 1