Tag: prove

Prove or disprove the following language is context free

The language $ L$ defined as: $ L = \{wtw^R | w,t \in \{0,1\}^\star \text{ and } |w| = |t| \}$

It looks like the language can be “pump” by context free pumping lemma, but pumping lemma doesn’t prove the language is context free. So I’m thinking to build a PDA that recognized it. But I’m stuck on constructing the PDA, my initial thought is using nondeterminism to guess the string $ w$ and $ t$ , then compare the values after $ t$ which is string $ w^R$ . But still hard for me to come up a whole construction at this moment, any suggestions?

Prove that the language $\{a^ib^i | i\geq 0\}$ is not regular? (Do we just consider $a^nb^n$, where $n$ is the pumping length?

I think to prove that $ \{a^ib^i | i\geq 0\}$ is not regular, we just have to consider the string $ a^nb^n$ (which is in the language) and apply the pumping lemma. But I’m not sure how to proceed using the pumping lemma (even though I know it applies with our choice of string, since the string is at least $ n$ long).

How can I prove that my greedy algorithm for least guards is optimal?

This is the problem:

An art gallery hired you to put guards so they can monitor artworks in a hallway. The goal is to minimize the amount of guards needed in this hallway. Each guard has a range of 10 meters (5m on the right, 5m on the left with him being in the middle).

No matter where the artworks are put in the hallway we want the minimal amount of guards as possible.

My Greedy Algorithm:

Start at the beginning of the hallway. Find the position of the closest artwork from the entrance. Put the guard at position closest artwork + 5m ahead. Eliminate all the artworks covered by the guard. Re-do the process but this time start where the range of the previous guard ended

Now how do I write a proof for this? How do I prove that my algorithm is indeed optimal? Which mathematical proof techniques can I use?

How do I prove regular/non-regular with Nerode-Theorem? How to use it?

$ L_{1}=\left\{w \in\{a, b\}^{*} | \#_{a}(w)=0\right\}$

$ L_{2}=\left\{w \in\{0,1\}^{*} | w=u v u \text { with } u, v \in\{0,1\}^{*}\right\}$

I have problems to prove regularity with the nerode theorem

The idea behind this is that the nerode classes have to be finite for a regular language

How do I use this?

For L1 I know this

There is only $ b^{n}$ due to the fact that there language does not accept any a

Let m$ \neq$ n than there exists $ b^{n}b$ and $ b^{m}b$ for all m $ \in \mathbb{N}$ \n an n $ \in \mathbb{N}$ \m and of all them are in L

For 2 I know this

Let vu be x so for all a,b $ \in \{0,1\}^{\star}$ ax an bc are in L.

How to prove by induction on the length of the input string?

The string is $ $ S = \{(ab)^k | k \geq 1 \}$ $

The NFA enter image description here

I’m new learning formal language and I understand how to prove mathematical induction. However, when it turns into a string or NFA stuff, I’m stuck on what induction hypothesis do I have to make(or writing the proof formally). Have been stuck for a while, what’s a good way to start an approach?

prove that log((n^2)!)= o(log((n!)^2))

i have a question – how i can prove that:

$ \log((n^2)!) =\theta (log((n!)^2))$

i try something like that:

$ \log((n^2)!) = 2*(log(n)!)=\theta(2*(log(n)!)=\theta(n\ log(n)) $

$ \ \theta(log(n!)^2)=\theta(log(n!)*log(n!)) = \theta(n\ log(n)) $

then we can see that is equal –> there are $ \theta(n\ log(n))$

this is true?

How to prove the language of suffixes of a regular language is still regular?

Prove that if $ L \subseteq \Sigma^\star$ is regular, $ L’$ is also regular where

$ $ L’ = \{w\mid{uw \in L \mbox{ for some string }u \in \Sigma^\star}\}$ $

I’m new learning formal language and haven’t proved stuff like this. But I’m sharing my thoughts here to make sure I’m on the right track. The first idea came to my mind is using close properties. Since $ u$ $ w$ $ \in$ L and $ u$ $ \in$ $ \Sigma^\star$ so we know L is also regular. $ L’$ is the concatenation of two regular languages. The regular languages are closed under concatenation thus $ L’$ is also regular.

Any feedback or suggestions?

Find and prove a linear algorithm that identifies all cycles and the length in a graph where each vertex has exactly one outgoing edge


Consider a directed graph on n vertices, where each vertex has exactly one outgoing edge. This graph consists of a collection of cycles as well as additional vertices that have paths to the cycles, which we call the branches. Describe a linear time algorithm that identifies all of the cycles and computes the length of each cycle. You can assume that the input is given as an array A, where A[i] is the neighbor of i, so that the graph has the edge (i, A[i]).

I kind of have an idea of how to approach the algorithm but have no idea what to do with the proof of my algorithm. So far I’m thinking of marking the vertices I have traversed, and every time a vertex points back to the ones that I’ve traversed I count one cycle and move on to the next unvisited vertex.

However, I am also very confused by the wording. Maybe I’m missing something and not understanding what the branches are supposed to do: am I right to assume that if the graph is connected (this graph can also be disconnected) and each edge only has one outgoing edge, there will only be one cycle? Since having just two cycles would require a vertex to point to two vertices and contradict the premise.

Can I use the following method to prove an algorithm is correct?

I’m trying to show that a solution I have obtained via an algorithm is correct. The way I plan on doing this is first by showing that an optimal solution does indeed exist. Then, I plan on showing that every other solution that is not the solution provided by my algorithm cannot be optimal. Finally, I show that the solution I have cannot be improved in the same way as any other solution.

Is this enough to show that my algorithm is optimal? In this case I am avoiding doing an “exchange argument” a la greedy algorithms. In fact, I don’t really prove anything about how my solution is an improvement of the other ones, but simply that all of the other ones can be improved, and given that an optimal solution exists, the one I have must be it because it cannot be improved in the same way that the other ones can.