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$

lesson_01.md 2.2 KB Geschiedenis Ruwe