Unit 1: Introduction to the Theory of Languages and Automata.

Introduction:
The objective of this unit is to identify the theoretical and necessary concepts.
about the subject theory of languages and automata 1.

Unit 1 - Introduction to Formal Language Theory.

1.1 Alphabet
An alphabet is a non-empty finite set whose elements are called symbols.
We denote an arbitrary alphabet with the letter Σ.

Symbols:
It is an abstract entity that cannot be defined, as it would remain as a
Axiom. Just as a point is defined in geometry. Which normally the
symbols are letters (a, b, c, ... z), digits (0, 1, ... 9, characters (+, -, *, /, >, < ...).
The symbols can be made up of several letters or characters.

Alphabet:
The alphabet is a set of letters, with a specific order.
We could precisely say that the alphabet is a set of letters
(characters or graphemes) of a writing system, each one represents
approximately one phoneme (consonant or vowel).

1.2 Chains.
A string or word over an alphabet Σ. we admit the existence of a
the only string that has no symbols, which is called an empty string and is
denotes with λ. the empty string plays, in the theory of formal languages,
a role similar to that played by the empty set Ø in the theory of
sets.
String length.
The length of a string is the number of symbols it contains. The notation
the employee is the one indicated in the example:
We use the strings from the examples:
I abcb I = 4,
I a + 2*b I = 5
I 000111 I = 6
If a > b then a = b; I = 9

Empty Chain.
An empty string is the only string of characters with size zero. And the
we can usually denote with the letters λ or Є (Greek).
String concatenation.
The concatenation of two strings u and v, written uv, is "gluing" the two strings together.
to form a new one.
Example:
Let u = ab
v = ca
w = bb. Then
uv = abca
uw = cabb
(uv) w = abcabb
u(vw) = abcabb

The result of concatenating u, v, and w is independent of the order in which.

the operations are executed. Mathematically this property is known
like associativity.

Universe of discourse.
It is a set of all the strings that we can form with symbols from
We call alphabet V the universe of discourse of V and represent it from the
next way W(V). It is evident that W(V) is an infinite set and that the
The empty string belongs to W(V).
Example:
An alphabet with a single letter V = { a }, we can say that the universe of
The language is: W(V) = { λ, a, aa, aaa, aaaa,....} and thus contains a series of strings.
infinite.

1.1 Languages.
It is a set of strings, from all the selected ones from a Σ*. where Σ
a determined alphabet is called a language. If Σ is an alphabet and L Σ*,
then L is a language of Σ. Note that a language of Σ does not need
include strings with all the symbols of Σ, since once we have this
L is a language of Σ, we also know that it is a language of any.
alphabet that is a superset of Σ.
The choice of the term 'language' may seem strange. However, the
common languages can be interpreted as sets of strings. A
an example would be English, where the collection of the correct English words
It is a set of strings from the alphabet that consists of all the letters. Another
An example is the C language.

1.2 Types of languages.

Natural language (Spanish)

We are associated with the traditional concept of grammar that,
in this intuitive way, we can consider a set of rules that allows us
they indicate what is correct and what is not in natural language. To this end
We can get closer to the clearest and most formal definition of the Spanish language.

Artificial language.
In this language, we apply the same method in which we define a
fragment of the programming language. Where we intend to describe the
instructions which allows us to assign a value to an expression or to a
variable in a C language.

Regular language.
We call them languages because their words contain "regularities" or
repetitions of the same components, for example in this language L1 =
In this example we can appreciate the words
L1 is just repetitions of 'ab' where it repeats several times. Its
regularity consists of words that contain 'ab' several times.

1.5 Computer tools linked with languages.

Translator.
A translator is a program that takes a text written in a
language (source language) and outputs a written text in a
language (object language) that preserves the original meaning.
Examples of translators are assemblers and compilers.

Compiler.
The compiler is a computer program that translates a program written in
programming language and it is converted to programming language, we can
to say that this program allows us to translate source code of a program
in high-level language, and we pass it to another lower level (machine language).

Assemblers.
The assembler is the program in which the traction of a program is carried out.
written in assembly and converts it to machine language. Direct or indirect the
translation in which the instructions are nothing more than instructions that it executes
the computer.

Interpreters.
Interpreters usually perform two operations:
They translate the source code to an internal format.

Execute or interpret the program translated into the internal format.

Where the first belongs to the interpreter, which sometimes calls the compiler,
this is how the internal code is generated, but it is not machine language, nor language
of symbols, much less a high-level language.

Conclusion
In this way, the theoretical concepts of alphabet, string, symbol were seen.
length of the string, etc. As well as each of its topics and subtopics.