How do I define a string in formal language by means of a definition of tuple?

526 Views Asked by At

I'm constructing mathematical notions and definition from the bottom of the mathematical structure. So whenever I learn, or encounter new concepts, I try to define it step by step, without using any informally premised concepts, even if they look obvious (except primitive notions, of course.).

String in formal language is, informally speaking, a juxtaposition of finitely many symbols. I think, to define this term rigorously, we have to define order first. And I already defined ordered pair, or generally tuple which contains a concept of order. Roughly speaking, we can define an ordered pair by only adopting set-element concept, $(a,b)=\{a,\{a,b\}\}$. I think this definition is the most foundational way to define order.
So I tried to define string by means of this concept, but having problem as I already defined tuple. How do I define string in a very foundational way?

1

There are 1 best solutions below

0
On

A word $w$ in the context of formal languages and automata theory is a sequence of symbols from an alphabet $\Sigma$

$$ w \in \Sigma^I = \{ \varphi : I \to \Sigma \} $$

for some index set $I$.

The usual set theoretic modeling for sequences and maps apply.

Symbol and alphabet are just different names for element and non-empty set.

A set of words is called a language.

The length of a word is $|w| = \mbox{card}(I)$.

A special word is $\varepsilon$ the word of length $0$, the empty word. It is the neutral element of the concatenation operation

$$ \cdot : \Sigma^* \times \Sigma^* \to \Sigma^* \\ \cdot(u,v) = uv $$

with $|uv| = |u| + |v|$ and $uv$ having the first $|u|$ sequence elements like $u$ and the remaining $|v|$ like $v$, where I used the set of finite words $\Sigma^*$

$$ \Sigma^* = \cup_{n \in \mathbb{N}_0} \Sigma^n $$

where $\Sigma^n$ is the set of words of length $n$ over $\Sigma$, while one can define infinite words as well (see Büchi automata).

See Free Monoid for a more algebraic perspective.