5

What is the value of the Boolean function f(x, y, z) = (x bar + y bar)z + xyz when x = 1, y = 0 and z = 1? Prove or disprove that xy + y = y whenever x and y are Boolean variables. How many different Boolean functions are there of degree 3? Find the sum-of-products expansion of a Boolean function f(x, y, z) that is 1 if and only if x = y = 1 and z = 0, or x = 0 and y = z = 1, or x = y = 0 and z = 1. What is the output of the following circuit? The productions of a phrase-structure grammar are S rightarrow S1, S rightarrow 0A, and A rightarrow 1. Find a derivation of 0111. What language is generated by the phrase-structure grammar if the productions are S rightarrow S11, S rightarrow lambda where S is the start symbol? Construct a finite-state machine that models a vending machine accepting only quarters that gives a container of orange juice when 50 cents has been deposited, followed by a button being pushed. (The possible inputs are quarters and the button, and the possible outputs are nothing, orange juice, and a quarter. The machine returns any extra quarters.) Suppose that A = (1, 11, 01) and B = {0, 10}. Find AB and BA. Let A = {1, 10}. Which strings belong to A*? What is the output produced by the following finite-state automaton when the input string is 11101? Which strings belong to the set represented by the regular expression 0* U 11