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

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?

-
can't you do the same thing? $(a,b,c)=\{a,\{a,b\},\{a,b,c\}$ – Carry on Smiling Jul 3 '14 at 21:26
@Bananarama I don't get your point. Of course I can do the same thing and also can generalize to n-tuple. BTW, your definition is wrong, if we use inductive way. – Novice Jul 3 '14 at 22:00
Wait, is it just ok to think string as tuple? For example, can we think a string $math$ as $(m,a,t,h)$? Should I define $string$ $notation$, which removes every commas and parentheses? Oh wait, isn't it so called $polish$ $notation$? – Novice Jul 3 '14 at 22:01
Is polish notation of a tuple is a string?! – Novice Jul 3 '14 at 22:04
@novice, I don't know, I'm merely giving my opinion, take a chill pill. – Carry on Smiling Jul 3 '14 at 22:12

## 1 Answer

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.

-