I Formal language question

[qqGlebqq]

I've been trying to study formal systems and so what i do not understand about formal languages is why we can define a "word" as a sequence of symbols. Some sources say a sequence here is a function, but we don't have set theory yet. So my question is what is a sequence in the definition of a "word". Is it a function or something else? By something else I mean that in some books, like in Kleene's Intro to maths it seems to me like sequence is just a bunch of signs written on paper

 

[fresh_42]

... it seems to me like sequence is just a bunch of signs written on paper

Yes, with the constraint that order matters. It is an ordered bunch of signs: $\text{tied}\neq \text{tide}.$

I use the word word informally as a finite ordered set of letters, which I call the alphabet. To make it a language, we need a set of acceptable words among all possible bunches of signs $\Sigma$, e.g. $\text{teid} \not\in \text{English}$ and a transition function $\delta : S\times \Sigma \longrightarrow \Sigma$ where $S$ is the finite set of possible states in which are automaton that accepts the language can be. I suspect that you are currently confusing this transition function with the term word.

The investigation of formal languages requires many very formal definitions to get rid of the ambiguity spoken languages intrinsically have.

 

[qqGlebqq]

Thank you!
You use the transition function (so you use set theory) in definition of formal language (and also "ordered set") , but as we didn't have FL, we didn't have set theory, so it becomes circular, no? I think I don't get from what we start and what we have in the beginning. Maybe you could advice me a book which would also help me with this confusion?

 

[fresh_42]

Thank you!
You use the transition function (so you use set theory) in definition of formal language (and also "ordered set") , but as we didn't have FL, we didn't have set theory, so it becomes circular, no? I think I don't get from what we start and what we have in the beginning. Maybe you could advice me a book which would also help me with this confusion?

I wouldn't call it set theory. We have to use the fundamental concept of a set without bothering any logical fallacies like Russel's paradox. Just the way you learned about the set of integers or the set of rational numbers. You can add numbers without knowing about set theory, can't you? Accepting a set as a collection of elements is sufficient in this context. Of course, some fundamental terms like empty set, subset, power set, union, intersection, and complement will be useful. That is Venn diagrams, not set theory.

And, yes, we need order very much because of the examples I gave. But that's just an enumeration. A set isn't ordered: $\{1,2,3\} = \{3,2,1\}$ but the (ordered / enumerated) sequences $(1,2,3)\neq (3,2,1).$ That is basically it.

My book is not in English, and I don't have other recommendations. My approach would be to find lecture notes on the internet. E.g. a search by "formal language + pdf" brought me to
https://www.its.caltech.edu/~matilde/FormalLanguageTheory.pdf
on the Caltech server. This should be a reliable reference.

Note that definitions and notations can vary between authors and sources. My book defines an automaton as a quintuple. Others might have less or more.

Don't think about set theory for too long, unless it will be necessary. We only need sets as a container for things - unordered, and sequences if ordered. I can't rule out that logical subtleties of set theory won't become an issue at some stage in the theory of formal languages, but certainly not at the beginning.

 

[Gavran]

A sequence is an enumerated collection of objects in which repetitions are allowed and order matters. (From Wikipedia.)
Although in this case the word function is excluded from the definition, a sequence is still a function whose domain is an interval of integers.

There are other definitions of a sequence.
A sequence is a list of elements with a particular order. (From Wikipedia.)
A sequence is an arrangement of two or more things in a successive order. (From …)
A sequence is the following of one thing after another. (From …)