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

Solutions

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 1 year ago

Next > < Previous

Related Solutions

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.

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).

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)

Closure under Context-Free Languages Show that the following operations are closed under context-free languages: union concatentation...

Closure under Context-Free Languages Show that the following operations are closed under context-free languages: union concatentation Kleene star

Regular => Context-Free Give a proof by induction on regular expressions that: For any language A,...

Regular => Context-Free Give a proof by induction on regular expressions that: For any language A, if A is regular, then A is also context-free. You may assume that the statements from the previous Closure under Context-Free Languages problem are proved. R is a regular expression if RR is: a for some a∈alphabet Σ, the empty string ε, the empty set ∅, R1∪R2, sometimes written R1∣R2, where R1 and R2 are regular expressions, R1∘R2, sometimes written R1R2, where R1 and...

Let R[x, y] be the set of polynomials in two coefficients. Prove that R[x, y] is...

Let R[x, y] be the set of polynomials in two coefficients. Prove that R[x, y] is a vector space over R. A polynomial f(x, y) is called degree d homogenous polynomial if the combined degree in x and y of each term is d. Let Vd be the set of degree d homogenous polynomials from R[x, y]. Is Vd a subspace of R[x, y]? Prove your answer.

Subjects