2022 Developer Survey is open! Take survey.

# Questions tagged [induction]

Questions about mathematical induction and inductive proofs.

155 questions
Filter by
Sorted by
Tagged with
37 views

### Structural induction proof for reverse(push(as, bs)) = push(reverse(bs), reverse(as))

I need to prove: reverse(push(as,bs)) = push(reverse(bs), reverse(as)) where: ...
1 vote
51 views

### Language generated by $S \to aAb|Sb$, $A \to aAb|ab$

Let $G = (\{A,S\}, \{a,b\}, S, P\}$ be the grammar with the following productions: \begin{align} & S \to aAb | Sb \\ & A \to aAb | ab \end{align} What is the language $L(G)$ generated by the ...
22 views

37 views

### Proving that a property is k-inductive with an SMT solver (parametric resettable counter)

I'm following the slides at https://homepage.cs.uiowa.edu/~tinelli/talks/FT-11.pdf where Tinelli explains how k-induction works in the context of SMT based model checking. A parametric and resettable ...
1 vote
250 views

### Proving a DFA recognizes a language using induction

The following DFA recognizes the language containing either the substring $101$ or $010$. I need to prove this by using induction. So far, I have managed to split each state up was follows: q0: ...
I'm given this "sorting" algorithm and now I'm supposed to prove, that if given an array of integers of length $n$, sort(A,0,n-1) will sort it. ...