# Basic Computer Science

There is a couple of very basic definitions and axioms in computer science. I consider them to be very important, because everything that comes later is based on them. And if you don’t fully comprehend the basic stuff, it will be very hard to understand anything further. That’s why I decided to write a whole post on these trivial definitions.

## An Alphabet

Yeah, I’m not kidding. There’s a formal definition for alphabet. And what’s worse: it actually makes sense. I just wonder what would a kindergartener say on this :-D. Anyway, here it goes:

**Definition 1.1.** An **alphabet** is a finite non-empty set of *symbols.*

Alphabets are usually denoted by Greek big sigma * Σ*. A set

*can be referred to as alphabet when it’s not empty, but also not infinitely big.*

**Σ***Σ = {a, b, c}*is an alphabet*Σ = {0, 1}*is an alphabet*Σ = {}*is**NOT**an alphabet*Σ = all integers*; is**NOT**an alphabet

Content of an alphabet are *symbols*. A symbol is some indivisible or atomic
unit that can have some meaning (not necessarily). For example, if *Σ =
{righteous, dude}* were alphabet, **righteous** and **dude** would be
considered to be atomic indivisible elements (even though they contain multiple
characters). Some folks also choose to omit the *finite* word from the
definition. But that’s for some very advanced stuff and I’m guessing that
finite alphabets will be more than sufficient for us.

## String

Another fundamental thing is a string. **String** or a **word** is a sequence
of some symbols (the order is important). Strings usually contain symbols from
only one alphabet. In that case we say string *x* over *Σ* is
a finite sequence of symbols from *Σ*. The formal definition is this:

**Definition 1.2**. Let *Σ* be an alphabet.

- empty string
*e*is string over*Σ* - if
*x*is a string over*Σ*and*a in Σ*is a symbol from*Σ*, then $latex xa$ is a string over*Σ* *y*is string over*Σ*only when we can derive it by applying rules 1 and 2.

There are some more basic definitions like string length, concatenation, reversation that are useful and important, but they might be a little intimidating at first, so let’s skip ahead to languages.

## Language

What is a **formal language**? We need to define *Σ ^{*}* first.

*Σ*is a set of all existing strings over alphabet

^{*}*Σ*. For example, let

*Σ = {0, 1}*, then _Σ

^{*}=

*{*e

*}*u

*{*all positive binary numbers

*}*.

Then a formal language **L** over alphabet *Σ* is a subset of
*Σ ^{*}*. Formally said, _L ≤ Σ

^{*}. Basically, language is a

*set of strings*. In context of programming languages, a language would be a set of all possible programs in that programming language. You see, that in most practical cases the set will be

**infinite**(as it is in the programming language case). So, it’s not very practical to describe languages by enumerating all possible sentences of the language. One way of describing a language is with things called

**formal grammars**. But we’ll get on to that later.