sigma star (discuss.tchncs.de)

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".

top 15 comments
sorted by: hot top new old
[-] Rentlar@lemmy.ca 11 points 2 weeks ago

This is just a representation of your feelings in Big-O notation.

[-] AlmightySnoo@lemmy.world 4 points 2 weeks ago

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

[-] kogasa@programming.dev 7 points 2 weeks ago* (last edited 2 weeks ago)

Automata and formal languages were pretty much my entire "Theory of Computation" class. It's what's in Sipser.

[-] Mars@beehaw.org 2 points 2 weeks ago

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

[-] fl42v@lemmy.ml 7 points 2 weeks ago

Sum asterisk or something? 🙃

[-] lemmesay@discuss.tchncs.de 23 points 2 weeks ago

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.

[-] PlexSheep@feddit.de 3 points 2 weeks ago

Can images work as formal Languages?

[-] lemmesay@discuss.tchncs.de 3 points 2 weeks ago

what'd a symbol be? a pixel?

aside from this, they say a picture is worth a 1000 words. so maybe a big language.

[-] Mars@beehaw.org 3 points 2 weeks ago

A tree can be seen as a formal language. Look into L-systems.

If you generalize what a symbol is (the rgb value of a pixel) you can write a grammar that ends producing a list of pixels. You can then place it in a 2d matrix and you have an image.

I guess a better approach would be wave function colapse, but seems to me like it could be formally described as a grammar (CS or CF, dunno, would have to look into it)

[-] AlmightySnoo@lemmy.world 2 points 2 weeks ago* (last edited 2 weeks ago)

wait until you learn about sigma-algebras in measure theory

[-] FishFace@lemmy.world 3 points 2 weeks ago

They don't have anything to do with alphabets in theory of computation...

[-] AlmightySnoo@lemmy.world 1 points 2 weeks ago* (last edited 2 weeks ago)

correct, but will come up if OP chooses to study measure-theoretic probability theory

[-] lemmesay@discuss.tchncs.de 1 points 2 weeks ago

thanks for sharing. can't wait to go insane :')

this post was submitted on 21 Nov 2023
71 points (86.6% liked)

Programmer Humor

2 readers
72 users here now

Post funny things about programming here! (Or just rant about your favourite programming language.)


founded 4 years ago