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
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.
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.
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)
You are not logged in. However you can subscribe from another Fediverse account, for example Lemmy or Mastodon. To do this, paste the following into the search field of your instance: !programmerhumor@lemmy.ml
Post funny things about programming here! (Or just rant about your favourite programming language.)
Rules:
Posts must be relevant to programming, programmers, or computer science.
No NSFW content.
Jokes must be in good taste. No hate speech, bigotry, etc.
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
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
Automata and formal languages were pretty much my entire “Theory of Computation” class. It’s what’s in Sipser.
This is just a representation of your feelings in Big-O notation.
neither an understatement nor an overstatement, a Big-Theta
wait until you learn about sigma-algebras in measure theory
thanks for sharing. can’t wait to go insane :')
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
Sum asterisk or something? 🙃
sigma star.
if you haven’t heard about theory of computation, let me define some keywords:
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.
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.
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)