lesson_01.md 2.2 KB
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$