Let swap_every_two be an operation on languages that is defined as follows: swap_every_two(L) = {a2a1a4a3 ....

Let swap_every_two be an operation on languages that is defined as follows:

swap_every_two(L) = {a2a1a4a3 . . . a2na2n−1 | a1a2a3a4 . . . a2n−1a2n ∈ L where a1, . . . , a2n ∈ Σ} In this definition, Σ is the alphabet for the language L. (it is a2a1a4a3 not a^2a^1 !!)

1. What languages result from applying swap_every_two to the following languages:

(a) {1^n | n ≥ 0}, where the alphabet is {1}.

(b) {(01)^n | n ≥ 0}, where the alphabet is {0, 1}.

2. Show that if L is a regular language then so it swap every two(L).

Solutions

Expert Solution

venereology answered 2 days ago

Next > < Previous

Related Solutions

Let L be the set of all languages over alphabet {0}. Show that L is uncountable,...

Let L be the set of all languages over alphabet {0}. Show that L is uncountable, using a proof by diagonalization.

Assume that an operation * is defined as follows: x * y = x' + y...

Assume that an operation * is defined as follows: x * y = x' + y Using Boolean algebra theorems and postulates (don’t use K-maps), check whether the operation * is associative or not?

An operation * is defined for two-valued variables a and b as follows: a*b = ab+a’b’

An operation * is defined for two-valued variables a and b as follows: a*b = ab+a’b’Let c = a*b. Determine which of the following identities are valid:a = b*ca*(bc) =1

Let M be defined as follows M = (K, Σ, s, ∆, F ) for K...

Let M be defined as follows M = (K, Σ, s, ∆, F ) for K = {q0, q1, q2, q3, }, s = q0, Σ = {a, b, c}, F = {q0, q2, q3} and ∆ = {(q0, abc, q0), (q0, a, q1), (q0, e, q3), (q1, bc, q1), (q1, b, q2), (q2, a, q2), (q2, b, q3), (q3, a, q3)}. 1. (1pts) Draw the diagram of M 2. (6pts ) DRAW a diagram of an automata M0 such...

Let D(x, y) be the predicate defined on natural numbers x and y as follows: D(x,...

Let D(x, y) be the predicate defined on natural numbers x and y as follows: D(x, y) is true whenever y divides x, otherwise it is false. Additionally, D(x, 0) is false no matter what x is (since dividing by zero is a no-no!). Let P(x) be the predicate defined on natural numbers that is true if and only if x is a prime number. 1. Write P(x) as a predicate formula involving quantifiers, logical connectives, and the predicate D(x,...

1. Average Cost for Producing Microwaves Let the total cost function C(x) be defined as follows....

1. Average Cost for Producing Microwaves Let the total cost function C(x) be defined as follows. C(x) = 0.0003x3 − 0.02x2 + 103x + 3,600 Find the average cost function C. C(x) = Find the marginal average cost function C '. C '(x) = 2. Marginal Revenue for Producing Loudspeakers The management of Acrosonic plans to market the ElectroStat, an electrostatic speaker system. The marketing department has determined that the demand for these speakers is represented by the following function,...

Give a grammar that generates each of the following languages: (1) L = {a2n cm bm...

Give a grammar that generates each of the following languages: (1) L = {a2n cm bm | m ≥ 0, n ≥ 0} (2) L = {an b2m cn | m ≥ 0, n ≥ 0} (3) L = {an bm | n+m is even} (4) L = {an bm | n ≤ m+3} (5) The complement of the language L = {anbn | n ≥ 0}

Let G be a group with the binary operation of juxtaposition and identity e. Let H...

Let G be a group with the binary operation of juxtaposition and identity e. Let H be a subgroup of G. (a) (4 points) Prove that a binary relation on G defined by a ∼ b if and only if a−1b ∈ H, is an equivalence. (b) (3 points) For all a ∈ G, denote by [a] the equivalence class of a with respect to ∼ . Prove that [a] = {ah|h ∈ H}. We write [a] = aH and...

Given two languages A and B, let A/B denote the language {w | w x ∈...

Given two languages A and B, let A/B denote the language {w | w x ∈ A for some x ∈ B}. Show that if A is a context-free language and B is a regular language, then A/B is a context-free language. hint (construct PDAs)

* Calculus****** * * + = ~.~ Let P1 be the plane defined by the equation...

******* Calculus************ * * + = ~.~ Let P1 be the plane defined by the equation 2x−8y+5z = 2 and let P2 be the plane defined by the equation 3x + 2y − z = 7. Find the equation for a new plane, P3, which is perpendicular to both P1 and P2, and also which passes through the point (-3,1,2). HINT: If P3 is perpendicular to P1 and P2, then the normal vector for P3 should be perpendicular to the...

Subjects