E.g. when proving L = {w in {a,b}^*: the first, the middle, and the last characters of w are identical}, can i just prove ab^pab^pa is not regular? Where p is the pumping length?

# Tag: Proving

## Proving injectivity for an algorithm computing a function between sets of different types of partitions [closed]

I am attempting to solve the following problem:

Let $ A$ be the set of partitions of $ n$ with elements $ (a_1, \dots, a_s)$ such that $ a_i > a_{i+1}+a_{i+2}$ for all $ i < s,$ taking $ a_{s+1} = 0.$ Define $ g_n = F_{n+2}-1$ and let $ B$ be the set of partitions of $ n$ as $ b_1 \ge \dots \ge b_s$ such that $ b_i \in \{g_n\}$ for all $ i,$ and if $ b_1 = g_k$ for some $ k,$ then $ g_1, \dots, g_k$ all appear as some $ b_i.$ Prove $ |A|=|B|.$

**Attempt:** Let $ e_i$ be the vector with $ 1$ at position $ i$ and $ 0$ elsewhere. If $ b_1 = g_k,$ let $ c=(c_k, \dots, c_1)$ count how many times $ g_i$ appears. We calculate $ f: B \to A$ as follows:

Let $ c=(c_k,\dots,c_1), a=(0,\dots,0).$ While $ c \ne 0,$ let $ d_1 > \dots > d_k$ be the indices such that $ c_{d_i} \ne 0.$ Replace $ c, a$ with $ c-(e_{d_1}+\dots+e_{d_k}), a+(g_{d_1} e_1 + \dots + g_{d_k} e_k)$ respectively. After the while loop ends, let $ f(b)=a.$

Let $ \sum a, \sum b, \sum c$ be the sum of the components of $ a, b, c$ respectively. Since $ \sum c$ decreases after every loop, the algorithm terminates and $ f(b)$ is well-defined. Since $ c_k g_k + \dots + c_1 g_1 + \sum a$ does not change after every iteration, is $ \sum b$ at the start and $ \sum a$ at the end, we have $ \sum f(b) = \sum b = n,$ so $ f(b)$ is also a partition of $ n.$ Now $ a = (g_k, \dots, g_1)$ after the first loop, which satisfies the condition $ g_i > g_{i-1}+g_{i-2}$ since $ g_i = F_{n+2}-1 = (F_{n+1}-1)+(F_n-1)+1 > g_{i-1}+g_{i-2}.$ Furthermore, after every iteration of the loop, the difference $ a_i – (a_{i-1}+a_{i-2})$ changes by $ 0, g_{d_j}-g_{d_{j-1}} > 0,$ or $ g_{d_j}-(g_{d_{j-1}}+g_{d_{j-2}}) > 0,$ so we have $ a_i > a_{i-1} + a_{i-2}$ at the end and hence $ f(b) \in A.$ Thus, $ f: B \to A$ is well-defined.

In order to prove the injectivity of $ f,$ it suffices to prove each loop iteration as a mapping $ (c,a) \to (c’,a’)$ is injective, which would imply the mapping $ (c,0) \to (0,a)$ that the while loop creates is injective. Indeed, if $ f(b_1) = f(b_2) = a$ with $ (c_1, 0), (c_2, 0)$ being sent to $ (0, f(b_1)) = (0,a), (0, f(b_2)) = (0,a)$ respectively, then we have $ (c_1, 0) = (c_2, 0) \Rightarrow c_1 = c_2 \Rightarrow b_1 = b_2.$

Suppose $ d_1 > \dots > d_i, f_1 > \dots > f_j$ are the non-zero indices of $ c_1, c_2$ respectively and $ c_1 – (e_{d_1}+\dots+e_{d_i}) = c_2 – (e_{f_1}+\dots+e_{f_j}), a_1+g_{d_1}e_1 + \dots+ g_{d_i} e_i = a_2 + g_{f_1} e_1 + \dots + g_{f_j} e_j.$ If $ x \ge 2$ is an entry of $ c_1,$ it decreases by $ 1,$ so the corresponding entry in $ c_2$ after $ c_2$ is modified is also $ x-1,$ which means it must’ve been $ (x-1)+1 = x$ before since $ x-1>0.$ Thus, if the values of two positions of $ c_1, c_2$ differ, one is $ 1$ and the other is $ 0.$ However, if $ c_1 = (1,0), a_1 = (3,1), c_2 = (0,1), a_2 = (4,1),$ then $ (a_1, c_1), (a_2, c_2)$ both get sent to $ ((5,1), (0,0)).$ I can rule out this specific example by arguing that one of the pairs is illegal and could not have come from any choice of initial $ c,$ but I have no idea on how to do this in general.

What should I do next in order to show $ f$ is injective? Furthermore, since the problem I’m trying to prove is correct, injectivity would imply $ f$ is secretly a bijection. But I have no clue on how to even start on the surjectivity of $ f,$ so I just constructed a similar algorithm for $ g: A \to B$ in the hopes of proving $ g$ is injective too. If I can show $ f$ is injective I will probably know how to show $ g$ is.

Here is an example of $ f, g$ in practice:

Let $ n = 41, b = (12, 7, 7, 4, 4, 2, 2, 2, 1) \Rightarrow c = (1, 2, 2, 3, 1).$

$ $ ((1, 2, 2, 3, 1), (0,0,0,0,0)) \to ((0, 1, 1, 2, 0), (12, 7, 4, 2, 1)) \to ((0, 0, 0, 1, 0), (19,11,6,2,1)) \to ((21,11,6,2,1),(0,0,0,0,0)),$ $ so $ f(b) = (21,11,6,2,1).$

Let $ a = (21, 11, 6, 2, 1).$

$ $ ((21,11,6,2,1),(0,0,0,0,0)) \to ((9,4,2,0,0), (1,1,1,1,1)) \to ((2,0,0,0,0),(1,2,2,2,1)) \to ((0,0,0,0,0),(1,2,2,3,1)),$ $ so $ g(a) = (12, 7, 7, 4, 4, 2, 2, 2, 1).$

## help with proving combinatorial identity [migrated]

seems hard to prove the next identity. i think the direction is through **combinatorics** reasons. thanks.

## Proving a certain primitive recursive function exists

Assume $ f\colon ω × ω → ω$ is a computable function. How can we prove that there is a primitive recursive function $ g\colon ω × ω → ω$ where the following holds:

$ ∀n [∃s(f(n, s) = 1) ↔ ∃k(g(n, k) = 1)]$

So for every $ n$ , there is an $ s$ such that $ f(n, s) = 1$ if and only if there is a $ k$ such that $ g(n, k) = 1$ .

Been working on this problem for a while now, if anyone could please help?

## proving $E_{TM}$ is undecidable using the halting language

How to prove that:

$ E_{TM} = \{\langle M\rangle\mid M \ is\ a\ TM\ and\ L(M)=\emptyset\}\notin R$ (is undecidable)

using the language:

$ H_{halt}=\{(⟨M⟩,w):M\ halts\ on\ w\}$ .

I tried to prove by contradiction that assuming $ E_{TM}\in R$ I have a Turing machine which decides $ E_{TM}$ and to construct with it a turing machine which decides $ H_{halt}$ but I don’t know how to do so.

## Proving the recurrence for the “number of ways to make change” problem

I’m studying the famous making change problem. (Post 1 and Post2).

Suppose you were given three coins (1, 2, and 5) and a bill of amount 10 and you want to compute the number of ways you could exchange the bill into coins. In this specific example, there are 4 ways.

The solution involves ordering the coins from the largest to the smallest (5, 2, 1). We then can divide the solution into three subproblems:

(1) the number of ways to change using coins (1) and amount (10 – 1). Call it $ F_1(10-1)$ .

(2) the number of ways to change using coins (1,2) and amount (10 – 2). Call it $ F_2(10-2)$ .

(3) the number of ways to change using coins (1,2,5) and amount (10 – 5). Call it $ F_3(10-5)$ .

The final recurrence would be $ F(10) = F_1(10-1) + F_2(10-2) + F_3(10-5)$ .

I understand the intuition and usually dynamic programming problems have very straight forward proofs (Cut and Paste Arugments). But with this problem, I have no idea where to start? The proof is usually by contradiction and arguing how it’s not possible for $ F(n)$ not to be the optimal value. But I’m not sure here. Any hints on how to even start with this proof? Basically, why is the above recurrence correct?

## Proving the language of a CFG with this rule [duplicate]

If I want to prove a language (e.g. $ L = \{ z \;|\; z \in \{x,y\}^*\}$ ) correct based on a context-free grammar, how can I do so if there exists a rule in the grammar

$ $ S \rightarrow xS \;|\; yS \;|\; \varepsilon$ $

I know that multiple applications of the rules $ S \rightarrow xS$ and $ S \rightarrow yS$ can lead to any string $ z \in \{x,y\}^*$ , but is there a specific way I can show this? I do not know how to articulate this step into my proof.

## N numbers, N/2 pairs. Minimizing the maximum sum of a pairing. Proving greedy algorithm

So say I have n numbers, where n is even. I want to pair the numbers such that the maximum sum of the pairs is minimized. For example -2, 3, 4, 5. The ideal pairing is (-2, 5), (3, 4), since its maximum sum is 7, and that is the minimal sum possible for a max sum in any pairing. The key to the algorithm is to sort the values from least to greatest. Then pair the least with the greatest, and so on, until you reach the center of the ordering.

Example: 3, -2, 4, 5

Algorithm sorts the values: -2 , 3, 4, 5

Then pairs first with last: (-2, 5)

Then pairs the next available first and last: (3, 4)

Terminates since no pairs left.

This is a greedy algorithm and I am trying to prove that it is always correct using a “greedy stays ahead” approach. My issue is that I am struggling to show that the algorithm’s maximum sum is always $ \leq$ optimal maximum sum. My intention was to suppose for contradiction that the optimal maximum sum is $ <$ the algorithm’s maximum sum. But I’m not sure how to find a contradiction. How would this proof go?

## proving that a turing machine which stops at every input and recognize the complement of L

i would like to prove that the deterministic TM M stops on every input and L(M) = L. Prove that there exists a deterministic TM M1 that stops on every input and recognizes the complement L of language L, that is L(M1) = L.

## Proving a language is context free without closure rules or grammar?

I know how to prove a language is context free through closure rules and through providing a grammar. However, in my exercises I’ve come across a language not suitable for either:

$ L = \{uc^nv\ \ |\ \ (2|v|_a + 3|v|_b) = (4|u|_a + |u|_b), n ≥ 1\}$

I know that pushdown automatons recognize context free languages, so providing a PDA that accepts this language would be enough to prove that it is context free.

How can I construct a PDA for this language?

I think rewriting the language contraint as the following would help, but I’m not sure how:

$ 2|v|_a + 3|v|_b – 4|u|_a – |u|_b = 0$

I can imagine it being something along the lines of `"every time you see an "a" in v, push 2 onto the stack, every time you see an "a" in u, pop 4 off the stack"`

, and something similar for b. If the stack has 0 elements, we’re in an accepting state.

However, I do not have experience with PDAs and I am having trouble drawing a diagram or formalizing this.