image transcription:
an image incorporating two famous memes. on top is the title “learning about Σ* in theory of computation.”
in the centre is a close-up of Chad face – often used when talking about sigma males – cropped in a five-pointed star shape.
below are two soyjaks pointing towards the aforementioned Chad face. those soyjaks are labeled “me” and “my brain”.
This is just a representation of your feelings in Big-O notation.
neither an understatement nor an overstatement, a Big-Theta
It’s funny, I never associated formal languages as part of the theory of computation. We only learnt about them from the perspective of automata/state machine theory
Automata and formal languages were pretty much my entire “Theory of Computation” class. It’s what’s in Sipser.
Sum asterisk or something? 🙃
sigma star.
if you haven’t heard about theory of computation, let me define some keywords:
- symbol: smallest unit. denoted by any character(a,b,c, etc.) or number (0,1, etc.)
- alphabet: set of symbols. denoted by Σ(sigma). e.g.: {a, b, c}
- string: sequence of symbols. eg: a, aa, aaab, etc.
- language: set of strings. e.g.: {a, as, aaab, …}
now, sigma has powers. Σ² is set of all strings of length 2. e.g.: {aa, ab, bb, …}. you can generalise this to Σ^n.
Σ* is union of all powers of sigma. i.e., Σ¹ + Σ² + …so, a language is basically a subset of Σ*.
as for why theory of computation even exists, you basically try to define what a computer can/cannot do.
and you try to mathematically define a computer. then you try to define what a language is(in case of programming , you need it to form languages and compilers). hence the need for this.
wait until you learn about sigma-algebras in measure theory
They don’t have anything to do with alphabets in theory of computation…
correct, but will come up if OP chooses to study measure-theoretic probability theory
thanks for sharing. can’t wait to go insane :')
Can images work as formal Languages?
what’d a symbol be? a pixel?
aside from this, they say a picture is worth a 1000 words. so maybe a big language.
