Please post your solutions to the Apr 19 In-Class Exercise to this thread.

Best, Chris

For the binary decision graph f(x), reduce all outputs to point to two nodes, one for accepting and one for rejecting. Now, replace the accepting node on f(x) with the entire graph g(y).

When f(x) has an output node as 1, replace that output node with the starting node for g(x).

given binary decision graphs f(x) and g(y), replace the accepting node of f(x) with the graph g(y) and point the rejecting node of g(y) to rejecting node of f(x)

To solve run g(x) on f(x) = 1.

We can reduce binary decision graph's t reuse nodes, such that g(n) would use the same nodes for 1 and 0, which could be done in time(f(n))+time(g(n))