Question

1. a. Let A = { < A,w > | A is a DFA that accepts w}, M is a Turing machine, and L(M) = A. Suppose M accepts the string p. p is in the form of < B,s > where B is a DFA, s is a string, and B accepts s.

   True

   False

b. A linear equation is in the form of ax + b where a and b are constants and x is a variable. Let x-intercept be the point in which the graph of a linear equation crosses the x-axis. Note that for a given linear equation f(x) and its x-intercept, f(x-intercept) = 0. Consider the problem of determining whether x-intercept of a linear equation is greater than 0. What would be an equivalent membership problem?

	a.	{ < p > | p is an x-intercept}
	b.	{ < p > | p is a linear equation and x-intercept of p is greater than 0}
	c.	{ < p > | p is an x-intercept that is greater than 0}
	d.	{ < p > | p is a linear equation}

Answer 1

a)

Answer: True

explanation :

Given M accepts p which is of form  < B,s >, and L(M) is A

and now by the definition of A

< B,s > where B is a DFA, s is a string, and B accepts s.

b)

Answer: B

{ < p > | p is a linear equation and x-intercept of p is greater than 0}