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”.
You must log in or register to comment.
This is just a representation of your feelings in Big-O notation.
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.
Didn’t you go into Turing machines and the Halting problem from that?
That was my intro into computation: regex, automatas, state machines, stack state machines, formal languages, grammars, Turing machines, Hanting Problem, P NP.
No, we went Automata, Finite State Machines, regex, grammars, set-theoretical and other mathematical formalisms
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.
