Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
can't you do the same thing? $(a,b,c)=\{a,\{a,b\},\{a,b,c\}$ –  Gamamal 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. –  Gamamal Jul 3 '14 at 22:12

1 Answer 1

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.