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.
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)
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.
Add comment