this post was submitted on 21 Nov 2023
76 points (87.3% liked)

Programmer Humor

32511 readers
420 users here now

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

Rules:

founded 5 years ago
MODERATORS
 

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 are viewing a single comment's thread
view the rest of the comments
[–] [email protected] 23 points 1 year 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.