The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
2answers
46 views

Prove correctness of DFA ending with ab

I have the following deterministic finite automaton and I am need to prove correctness of the claim that this automata accepts $\{wab \mid w\in \{a,b\}^*\}$ I know that I need to prove by induction ...
-1
votes
0answers
15 views

The substitution method for solving recurrences [duplicate]

I'm having a lot of trouble using the substitution method to solve the exercises in CLRS section 4.3. The explanation seems inadequate to solve the problems, there's no answers in the solution manual ...
0
votes
0answers
27 views

Solving Subproblem in Logic (first-order, propositional, pddl)

One sentence question Is there any algorithm able to prove (solve) a logic problem (first-order, propositional, pddl) by finite induction? Background I am researching Hierarchical planning solvers ...
0
votes
1answer
34 views

How do you prove two languages are equivalent using the definition of acceptance?

I need to prove that $L(f(M)) = L(M)\cup \{\varepsilon\}$ where $M$ is a DFA and $f$ is the function $f(M) := (Q\cup \{q_f\}, \Sigma, \delta', q_f, F\cup\{q_f\})$ and $q_f$ is a new state not in $Q$ ...
3
votes
2answers
38 views

How to pick a good structural induction hypothesis

(Full disclosure: homework question) Let $M = (Q, \Sigma, q_0, A, \delta)$ be a finite automaton. The extended transition function $\delta^*$ is defined as follows: $\forall q \in Q$ $\delta^*(q, ...
1
vote
1answer
37 views

Prove by Induction that $r_n$ is $O(\log_2(\log_2n))$ [duplicate]

Let the sequence $r$ be defined by: $$\begin{align*}r_{1} &= 1\\ r_n&= 1 + r_{\lfloor\sqrt{n}\rfloor}\,,\quad n\geq 2\,.\end{align*}$$ Prove by induction that $r_n$ is $O(\log_2(\log_2n))$. ...
0
votes
1answer
61 views

Structural induction over list

I want to prove that unique(reverse(L)) = reverse(unique(L)) where L is a List. List has the following constructors: ...
0
votes
1answer
42 views

Pierce's Types and Programming Languages : circular definition of terms?

In Pierce's book, on page 26-27 it is given a definition of terms for a simple language using inference rules. In the picture below it is marked by red highlighting the problematic part. What is ...
0
votes
1answer
58 views

How do I use induction to show that the language of a grammar is contained in a given set? [duplicate]

Given that I have the grammar $\qquad\displaystyle G_1 = (\{a, b, c, d\}, \{S, X, Y \}, S, \{S → XY, X → aXb, X → ab, Y → cYd, Y → cd\})$, how am I supposed to prove that $\qquad\displaystyle S(G1) ...
0
votes
0answers
24 views

Proof of the base case of Big Theta using induction [duplicate]

Here is a recursive definition for the runtime of some unspecified function. a and c are positive constants. $T(n)=a$, if $n=2$ $T(n)=2T(n/2)+cn$ if $n>2$ Use induction to prove that ...
1
vote
1answer
90 views

Proof of big theta using induction [duplicate]

Here is a recursive definition for the runtime of some unspecified function. $a$ and $c$ are positive constants. $T(n) = a$, if $n = 2$ $T(n) = 2T(n/2) + cn$ if $n > 2$ Use induction to prove ...
3
votes
1answer
54 views

Using induction to prove transition states are the same

Suppose that you have a DFA $M=\left(S,\Sigma,s_0,\delta,{s_f}\right)$ with $s_f\neq s_0$. Suppose further that, for all $a\in\Sigma$, $\delta\left(s_0,a\right)=\delta\left(s_f,a\right)$. Show that ...
10
votes
4answers
167 views

Is path induction constructive?

I'm reading through the HoTT book and I have a hard time with path induction. When I look at the type in the section 1.12.1: $$\text{ind}_{=_A}:\prod_{C:\prod\limits_{x,y:A}(x=_Ay)\to \mathcal{U}} ...
1
vote
1answer
346 views

Correctness of proof by induction

Suppose a person states the following: $n^2 = (n * n), \forall n > 0$. One can check such equality by saying, via proof by induction, that: for $n := 0:\ 0^2 = (0 * 0)$; for $n := 1:\ 1^2 = (1 * ...
-1
votes
1answer
204 views

induction proof for kleene star

i posted this on mathematics stack exchange here before i realised this one existed. i am going through some past exam paper questions on regular languages for some revision, and i am having a bit of ...
1
vote
3answers
578 views

How to find whether a grammar's language is finite or infinite?

I have this context-free grammar and I want to find out whether its language is finite or infinite. ...
1
vote
2answers
87 views

Rule induction principles in Harper's PFPL

I have a few small questions about section 2.4 ("Rule induction") in Practical Foundations for Programming Languages (p. 19). (1) In the rule induction principles for ...
0
votes
1answer
63 views

Mathematical Induction Problem from Concrete Abstractions

This is a problem from 'Concrete Abstractions' which is available free on the web[1]. It's a book similar to SICP. The problem: Exercise 2.16 Consider the following procedure foo: ...
-1
votes
2answers
201 views

Induction proof, base case not working but induction step works? [closed]

$1+3+5+...+(2n+3)=n^2+4n$ For this series using induction proof. Base case 1,2,3,.. not working. But induction step works well. Base case is not given in question.
2
votes
2answers
164 views

How to apply the substitution method to n/2?

I recently was introduced to solving recurrence bounds by substitution but there's something i don't understand about it. In standard induction proofs you prove a base case, assume it holds for n ...
1
vote
2answers
605 views

Language of balanced parentheses; Biconditional proof about parentheses

Let L be language of balanced parentheses. (a) Prove If there are equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'s, then w is in L. (b) Prove If w is in L, then ...
0
votes
2answers
3k views

Prove correctness of recursive Fibonacci algorithm, using proof by induction

I'm studying for the computer science GRE, and as an exercise I need to provide a recursive algorithm to compute Fibonacci numbers and show its correctness by mathematical induction. Here is my ...
1
vote
0answers
125 views

How to prove the asymptotic upper bound for $T(n) = 2T(\lfloor n/2\rfloor + 17) + n$ is $O(n \log n)$? [duplicate]

I met the problem Show that the solution to $T(n) = 2T(\lfloor n/2\rfloor + 17) + n$ is $O(n \log n)$ while reading Introduction to Algorithm. It's a question about the substitution method for ...
1
vote
0answers
66 views

Proving that a BST with N>=1 nodes will have log(N+1) levels

I am trying to prove by induction the following theorem: Use Induction to prove the following fact: for every integer, $N\ge 1$ , a BST with $N$ nodes must have at least $\log( N + 1)$ levels. I've ...
1
vote
0answers
625 views

Insertion sort Proof by Induction

I am reading Algorithm design manual by Skiena. It gives proof of Insertion sort by Induction. I am giving the proof described in the below. Consider the correctness of insertion sort, which we ...
0
votes
0answers
46 views

How i can use Mathematical induction to prove CFG production? [duplicate]

If I have production $G_n$ $S \rightarrow A_i b_i \quad$ for $1 \le i \le n$ $A_i \rightarrow a_j A_i \mid a_j\quad$ for $1 \le i$ and $i \ne j$ Prove $G_n$ is sub-productions from $2n^2 ...
5
votes
2answers
737 views

Finding nested intervals efficiently

The intervals are represented as two numbers, e.g. $(4.3, 5.6)$. The intervals are unique. If for $(x,y)$ and $(u,v)$, $x≤u$ and $v≤y$, $(u,v)$ is nested in $(x,y)$ How do I find out which ...
5
votes
1answer
1k views

Prove correctness of recursive multiplication algorithm

I'm in a first year discrete math course and we started algorithms. I created a recursive algorithm to multiply two numbers together: ...
9
votes
3answers
417 views

Do “inductively” and “recursively” have very similar meanings?

Do "inductively" and "recursively" mean very similar? For example, if there is an algorithm that determines a n-dim vector by determine its first k+1 components based on its first k components having ...
9
votes
1answer
3k views

How do I write a proof using induction on the length of the input string?

In my Computing Theory course, a lot of our problems involve using induction on the length of the input string to prove statements about finite automata. I understand mathematical induction, however ...
3
votes
1answer
265 views

How to prove that the pre-order tree traversal algorithm terminates?

I see structural induction the usual way for proving an algorithm's termination property, but it's not that easy to prove by means of induction on a tree algorithm. Now I am struggling on proving that ...
5
votes
1answer
541 views

Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$

Solving the recurrence relation $T(n) = 2T(\lfloor n/2 \rfloor) + n$. The book from which this example is, falsely claims that $T(n) = O(n)$ by guessing $T(n) \leq cn$ and then arguing $\qquad ...