# FLC - lesson 01
##### Luca Oddone Breveglieri
## Introduction

### What is a formal language?

Contrary to natural language, it is meant to communicate with machines.

A language is *formal* if its *syntax* (structure) and *semantic* (interpretation) are defined in a precise algorithmic way.

There is an effective procedure to verify the grammatical *correctness* of a phrase and determine its meaning.

###### It is a mathematical object composed by:
- An __alphabet__ and built over a
    - __grammar__ consisting in axiomatic rules
    - or an __automata__

### Hystorical notes

##### Years '50
- Chomsky proposes the mathematical model of a grammar (1956)

##### Years '60
- Connection between formal languages and automata
- Invention of formal grammars
- Development of automated compilation

##### Years '70-'80
- Formal language theory becomes a standard university discipline
- Introduction of SDKs like Flex or Bison

---

## Formal Languages, Basic Notions
### Definition of a language

- __Alphabet__: finite set of elements
- __String__: Ordered set of atomic elements, possibly repeated
- __Language__: Finite or infinite set of __strings__

__Strings__ can be both __finite__ or __infinite__.

The __cardinality__ of a *language* determines the number of elements contained,

It can be 0 for the __empty language__ or *infinite* for __infinite languages__.

---

### Operations on strings

#### Lenght of a string
Is the number of elements contained

$|bbc|=3\;\;\;\;|abbc|=4$

#### Equality of two strings
Two strings are equal if and only if
- They have the same length
- Their elements coincide in the same order

#### Concatenation (product of strings)
- Is a basic operation,
- Is associative,
- Changes the length.

es: $x=a_1a_2 \;\;\;\;\;y=b_1b_2b_3$

   $x.y=a_1a_2b_1b_2b_3=xy$

#### Empty string (or null string) $\varepsilon$:
 is the neutral element respective to concatenation

#### Substring:
Given a string x = u y v
- x is a prefix
- y is a substring
- v is a suffix

if u,v ≠ Ɛ,  y is a proper substring

#### Mirroring or Reflection
$x=atri\;\;\;\;x^r=irta$

#### Repetition or iteration
The m-th power of a string concatenates the string to itself for m-1 times

$x=ab\;\;x^0=\varepsilon$

$x^1=x=ab\;\;x^2=(ab)^2=abab$

---