62 lines
1.7 KiB
Markdown
62 lines
1.7 KiB
Markdown
---
|
|
type: math
|
|
---
|
|
## Induction
|
|
Similar (if not the same) to:
|
|
- [Mathematical Proofs (Induction)](Mathematical%20Proofs%20(Induction).md)
|
|
- [Structural Proofs](Proofs.md)
|
|
|
|
|
|
- Base case $0\in \mathbb{N}$
|
|
- Inductive step - if $n\in \mathbb{N} \implies n+1\in \mathbb{N}$
|
|
- We allow a finite number of steps
|
|
|
|
|
|
I.e.
|
|
Given $f (n) = n(n + 1)$ for all $n\in N$, then $f (n)$ is even.
|
|
|
|
**Base case:** $f(0) = 0\times 1 = 0$, which is even
|
|
**I.S.:**
|
|
$$
|
|
f(n+1) = (n+1)(n+2)= n(n+1)+2(n+1) = f(n) + 2(n+1) \blacksquare
|
|
$$
|
|
|
|
## Strings and Languages
|
|
Literally the same as [Mathematical Data Structures](Mathematical%20Data%20Structures.md), but on strings
|
|
|
|
How to define the reversal of a string, inductively?
|
|
|
|
|
|
Let $w$ be a finite string. We define $w^R$ by induction on $|w|$:
|
|
|
|
**B.C.:**
|
|
$|w| = 0$, then, trivially, $w = \epsilon \therefore w^R = \epsilon$
|
|
|
|
**I.S.:**
|
|
$|w| = n \geq 1$, so $w = u a$ with $|u| = n-1$,
|
|
|
|
|
|
## Operations on strings
|
|
- Concatenation (associative)
|
|
- Substring, prefix, suffix
|
|
- Replication (exponentiation): a string concatenated with itself
|
|
- Reversal ($u^R$)
|
|
|
|
## Operations on languages
|
|
- Lifting operations on strings to languages
|
|
- Concatenation of languages
|
|
- Kleene star - $V^*$ -> smallest superset[^1] of V that contains the empty string and is closed under concatenation, i.e. one or more repetitions
|
|
- Reversal
|
|
|
|
## Regular sets / languages
|
|
This used to be in DS, but I don't have it in this repo.
|
|
|
|
Recursively defined over an alphabet $\Sigma$ from
|
|
- $\emptyset$
|
|
- $\{\epsilon\}$
|
|
- $\{a\} | \forall a \in \Sigma$
|
|
|
|
Regex is a notatio nto denote regular languages, i.e.:
|
|
|
|
[^1]: The opposite of a subset - a set which contains all elements of another (and possibly more)
|