Show that {xx^R | x,y ∈ {0,1}*} is a context-free language. Note that x^R is the...

Show that {xx^R | x,y ∈ {0,1}*} is a context-free language.

Note that x^R is the reversal of x.

Show all work.

Question is for Discrete Math Structures

Expert Solution

Note:

A push-down automaton for the non-regular language L = { wwR | w ∈ {0, 1} * }. The input alphabet is {0, 1}.

It is convenient to use a and b as stack symbols as well. So ∆ = {0, 1}

In the initial state, a string is read and put on the stack. At some point the PDA guesses to be half-way the input, right after the string w and before the string w^R. Therefore, the PDA can switch non-deterministically to the second state, where the stack items will be compared with the input one by one. Note that the stack will be read in reversed order now as a stack is last-in first-out. Termination takes place when the stack is empty again.

The PDA is drawn for Equation:

Colby Messinger answered 2 years ago

Prove that the following language is context-free: L = { ω#x | ωR is a substring...

Prove that the following language is context-free: L = { ω#x | ωR is a substring of x and x, w ∈ {0,1}* } where ωR is ω reversed.

Suppose x,y ∈ R and assume that x < y. Show that for all z ∈...

Suppose x,y ∈ R and assume that x < y. Show that for all z ∈ (x,y), there exists α ∈ (0,1) so that αx+(1−α)y = z. Now, also prove that a set X ⊆ R is convex if and only if the set X satisfies the property that for all x,y ∈ X, with x < y, for all z ∈ (x,y), z ∈ X.

R is included in (R-{0} )x(R-{0} ) R = {(x,y) : xy >0} Show that R...

R is included in (R-{0} )x(R-{0} ) R = {(x,y) : xy >0} Show that R is an equivalent relation and find f its equivalent classes

Let X and Y be independent Gaussian(0,1) random variables. Define the random variables R and Θ,...

Let X and Y be independent Gaussian(0,1) random variables. Define the random variables R and Θ, by R2=X2+Y2,Θ = tan−1(Y/X).You can think of X and Y as the real and the imaginary part of a signal. Similarly, R2 is its power, Θ is the phase, and R is the magnitude of that signal. (b) Find the probability density functions of R and Θ. Are R and Θ independent random variables?

Prove the following Closure Properties with respect to Context Free Languages. 1. Show that Context Free...

Prove the following Closure Properties with respect to Context Free Languages. 1. Show that Context Free Languages are Closed under union(∪), concatenation(·), kleene star(*). (Hint: If L1 and L2 are Context Free languages then write Context Free grammar equivalent to L1 ∪ L2, L1 · L2, L∗ 1 ) 2. Show that if L1 and L2 are Context Free Languages, then L1 ∩ L2 is not necessarily Context Free. (Hint: Use Proof by Counter Example)

Let ∬[a,b]×[c,d]f(x,y)dA denote the integral of f(x,y)over the region with a≤x≤b and c≤y≤d. Find ∬[0,1]×[0,1]f(x,y)dA given...

Let ∬[a,b]×[c,d]f(x,y)dA denote the integral of f(x,y)over the region with a≤x≤b and c≤y≤d. Find ∬[0,1]×[0,1]f(x,y)dA given the following: ∬[0,1]×[1,5]f(x,y)dA=2, ∬[1,2]×[0,1]f(x,y)dA=−1, ∬[1,2]×[1,5]f(x,y)dA=4, and ∬[0,2]×[0,5]f(x,y)dA=3. Group of answer choices 2 -2 8 0 None of the above.

Let X,,X, and X, be independent uniform random variables on [0,1] Write Y = X, +X,...

Let X,,X, and X, be independent uniform random variables on [0,1] Write Y = X, +X, and Z = X+ X. a.) Compute E[X,X,X,. (5 points) b.) Compute Var(X). (5 points) c.) Compute and draw a graph of the density function fr. (15 points)

Question 1: Show that x = h + r cos t and y = k +...

Question 1: Show that x = h + r cos t and y = k + r sin t represents the equation of a circle. Question 4: Find the area above the polar x-axis and enclosed by r = 2−cos(θ). Question 5: If r = f(θ) is a polar curve, ﬁnd the slope of the tangent line at a point (r0,θ0).

Use Context-Free Pumping Lemma to prove that that following languages over the alphabet {'x', 'y', 'z'}...

Use Context-Free Pumping Lemma to prove that that following languages over the alphabet {'x', 'y', 'z'} are NOT context-free (a) {xjy2jzj : j > 0} (b) { xmynzk : m, n, k ≥ 0 and k = min(m,n) }

Consider two languages A and B where A is a context free language and B is...

Consider two languages A and B where A is a context free language and B is a regular language. Show that the set difference, A-B, must also be context free. Also show that B-A may not be context free

Question